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 |
迷宫类的问题,队列解法~~~大神指教#include<cstdio> #include<algorithm> #include<queue> using namespace std; char maze[25][25]; bool flag[25][25]; typedef pair<int, int> P; int main() { int m, n, sx, sy, x, y, nx, ny, i, j, len; P p; queue<P> que; while( scanf("%d%d%d%d", &m, &n, &sx, &sy) != EOF && m ) { sx--, sy--; for( i=0; i<m; i++) { scanf("%s", maze[i]); for( j=0; j<n; j++) flag[i][j] = false; } if( maze[sx][sy] == '.' ) { printf("0\n"); continue; } que.push(P(sx, sy)), flag[sx][sy] = true, len = 0;//将起点压入队列,并标记“浏览过” while( que.size() ) { p = que.front(), que.pop();//取出队首元素,并删除 x = p.first, y = p.second; for( i=-1; i<=1; i++) for( j=-1; j<=1; j++)//访问取出点周围得点 { nx = x + i, ny = y + j; if( nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == 'X' && !flag[nx][ny] ) que.push(P(nx, ny)), flag[nx][ny] = true; else if( (maze[nx][ny] == '.' || nx < 0 || ny < 0 || nx >= m || ny >= n) && i*j == 0 ) len++; //只有上下左右为'.'或越出边界时,长度加一 } } printf("%d\n", len); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator