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