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一次就过,附拙劣代码#include<stdio.h> #include<string.h> #include<queue> using namespace std; int vis[31][31][31]; char Map[31][31][31]; int step[35][35][35]; int l,r,c; int dir[6][3]={1,0,0, -1,0,0, 0,1,0, 0,-1,0, 0,0,1, 0,0,-1}; struct point { int x,y,z; } in,out,beg; int check(int x, int y, int z) { if(!vis[z][x][y]&&z >= 0&&z < l&&x >= 0&&x < r&&y >= 0&&y < c&&Map[z][x][y]!='#') return 1; return 0; } int bfs() { memset(vis, 0, sizeof(vis)); memset(step, 0, sizeof(step)); vis[beg.z][beg.x][beg.y] = 1; step[beg.z][beg.x][beg.y] = 0; queue<point>q; q.push(beg); while(!q.empty()) { out = q.front(); q.pop(); for(int i = 0; i < 6; ++i) { in.z = out.z+dir[i][0]; in.x = out.x+dir[i][1]; in.y = out.y+dir[i][2]; if(check(in.x, in.y, in.z)) { if(Map[in.z][in.x][in.y]=='E') return step[out.z][out.x][out.y]+1; q.push(in); vis[in.z][in.x][in.y] = 1; step[in.z][in.x][in.y] = step[out.z][out.x][out.y] + 1; } } } return -1; } int main() { while(~scanf("%d%d%d", &l,&r,&c)) { if(!l&&!r&&!c)break; for(int i = 0; i < l; ++i) for(int j = 0; j < r; ++j) scanf("%s", Map[i][j]); for(int i = 0; i < l; ++i) for(int j = 0; j < r; ++j) for(int k = 0; k < c; ++k) if(Map[i][j][k]=='S') { beg.z = i; beg.x = j; beg.y = k; } int ans = bfs(); ans==-1?printf("Trapped!\n"):printf("Escaped in %d minute(s).\n", ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator