| ||||||||||
| 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也TLE了,先谢了#include<stdio.h>
#include<queue>
using namespace std;
struct node
{
int xx,yy,zz;
};
int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int main()
{
int x,y,z;
while(scanf("%d%d%d%*c",&x,&y,&z)&&(x||y||z))
{
int i,j,k;
char map[34][34][34];
node start;
for(i=0;i<=x+1;++i)
for(j=0;j<=y+1;++j)
for(k=0;k<=z+1;++k)
map[i][j][k]='#';
for(i=1;i<=x;++i)
{
for(j=1;j<=y;++j)
{
for(k=1;k<=z;++k)
{
scanf("%c",&map[i][j][k]);
if(map[i][j][k]=='S') start.xx=i,start.yy=j,start.zz=k;
}
getchar();
}
getchar();
}
int kk=1,tt=0,level=0;
bool sign=false;
queue<node> bfs;
bfs.push(start);
while(!bfs.empty())
{
while(kk--)
{
node tmp;
tmp.xx=(bfs.front()).xx;
tmp.yy=(bfs.front()).yy;
tmp.zz=(bfs.front()).zz;
bfs.pop();
if(map[tmp.xx][tmp.yy][tmp.zz]=='E') {sign=true;break;}
map[tmp.xx][tmp.yy][tmp.zz]='#';
for(i=0;i<6;++i)
{
node tmp2;
tmp2.xx=tmp.xx+dir[i][0];
tmp2.yy=tmp.yy+dir[i][1];
tmp2.zz=tmp.zz+dir[i][2];
if(tmp2.xx<=0||tmp2.xx>x) continue;
if(tmp2.yy<=0||tmp2.yy>y) continue;
if(tmp2.zz<=0||tmp2.zz>z) continue;
if(map[tmp2.xx][tmp2.yy][tmp2.zz]!='#') tt++,bfs.push(tmp2);
}
}
if(sign) break;
kk=tt;
tt=0;
level++;
}
if(sign) printf("Escaped in %d minute(s).\n",level);
else printf("Trapped!\n");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator