| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:雁过留声——后缀数组+扫描In Reply To:看大家都用DSF和回溯,小弟我就改成用队列来实现了,果然可以AC,呵呵~ Posted by:gfedcba at 2009-01-12 21:34:49 > // 平时用栈来模拟回溯,这里我不用栈而用队列且不回溯也不深搜
> // 如有错误之处,望大牛提点迷津,谢谢
>
> #include <iostream>
> using namespace std;
>
> const int N = 20;
>
> int move[4][4]={{0,-1}, {0,1}, {-1,0}, {1,0}};
>
> bool Place(char room[][20], int i, int j, int w, int h) // 判断当前地点是否合格
> {
> if (i>=0 && i<=w-1 && j>=0 && j<=h-1 && room[i][j]=='.')
> {
> return true;
> }
> else
> {
> return false;
> }
>
> }
>
> struct Node
> {
> int i;
> int j;
> };
>
> int main()
> {
>
> char room[N][N];
> Node queue[N*N]={0};
> int front;
> int tail ;
>
> int count= 0;
> int w, h;
> int i, j;
> int mani, manj; // 标记人开始站的地点
> int way; // 移动路线
>
> while (cin>>h>>w && w!=0 && h!=0)
> {
> count = 0;
> memset(room, 0, sizeof(room));
> memset(queue, 0, sizeof(queue)); // 初始化时清空队列,RE过一次
> front = tail = 0; // 队头队尾也要初始化,RE过一次
>
> for (i=0; i<=w-1; i++) // 处理输入
> {
> for (j=0; j<=h-1; j++)
> {
> cin>>room[i][j];
> if (room[i][j] =='@')
> {
> mani = i;
> manj = j;
> }
> }
> }
>
> queue[tail].i = mani; // 将人所站的地点入队
> queue[tail].j = manj;
> room[mani][manj] = '!'; // 对room进行标记
> tail++;
> count++;
>
> Node temp;
> while (front != tail) // 如果队列为空,则表示将一个连通的地点区域都遍历完了
> {
> temp = queue[front];
> front++; // 出队
>
> for (way=0; way<=4-1; way++)
> {
> if (Place(room, temp.i+move[way][0], temp.j+move[way][1], w, h))
> {
> queue[tail].i = temp.i+move[way][0]; // 出队之后,将没有遍历过的地点入队
> queue[tail].j = temp.j+move[way][1];
>
> room[queue[tail].i][queue[tail].j] = '!';
> tail++;
> count++;
> }
>
> }
> }
> cout<<count<<endl;
>
> }
> return 0;
> }
HAO DE
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator