| ||||||||||
| 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