| ||||||||||
| 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 | |||||||||
bfs 1A/* 三维的走迷宫问题 */
/*
超时的注意用一个vis数组标记一下已经访问节点,可以缩短搜索队列的长度
*/
#include<iostream>
#include<queue>
using namespace std;
char map[35][35][35];
int vis[35][35][35];
int change[6][3]={1, 0, 0,-1, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 1, 0, 0,-1};
struct node
{
int x, y, z;
int step;
};
int l, r, c;
int sl,sx, sy;
int ex, ey;
int bfs(int th, int tx, int ty)
{
memset(vis, 0, sizeof(vis));
node a;
a.z = th;
a.x = tx;
a.y = ty;
a.step = 0;
vis[a.z][a.x][a.y] = 1;
queue<node> arr;
arr.push(a);
while (arr.size())
{
node t = arr.front();
arr.pop();
//cout <<t.z<<" "<<t.x<<" "<<t.y<<" "<< map[t.z][t.x][t.y] << endl;
if (map[t.z][t.x][t.y] == 'E')
{
return t.step;
}
for (int i = 0; i < 6; i++)
{
node s;
s.z = t.z + change[i][0];
s.x = t.x + change[i][1];
s.y = t.y + change[i][2];
if (s.z >= 1 && s.z <= l&&s.x >= 1 && s.x <= r&&s.y >= 1 && s.y <= c&&!vis[s.z][s.x][s.y] && map[s.z][s.x][s.y] != '#')
{
s.step = t.step + 1;
vis[s.z][s.x][s.y] = 1;
arr.push(s);
}
}
}
return -1;
}
int main()
{
while (cin >> l >> r >> c, l + r + c)
{
for (int i = 1; i <= l; i++)
for (int j = 1; j <= r; j++)
for (int k = 1; k <= c; k++)
{
cin >> map[i][j][k];
if (map[i][j][k] == 'S')
{
sl = i; sx = j; sy = k;
}
}
int res=bfs(sl, sx, sy);
if (res == -1)
cout << "Trapped!" << endl;
else
cout << "Escaped in " << res << " minute(s)." << endl;
}
system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator