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