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