题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1253
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 33222 Accepted Submission(s): 12255
思路:最基本的BFS题目。算是BFS的模板题吧!直接上代码吧!注意:因为是在立体空间中,所以有六个方向可走。
附上AC代码:
#include <bits/stdc++.h> using namespace std; const int dir[6][3] = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}}; const int maxn = 55; struct node{ int x, y, z, step; }; int mp[maxn][maxn][maxn]; bool vis[maxn][maxn][maxn]; int a, b, c, d; bool check(int x, int y, int z){ if (x<1 || x>a) return false; if (y<1 || y>b) return false; if (z<1 || z>c) return false; return true; } int bfs(int x, int y, int z){ vis[x][y][z] = true; queue<node> q; while (!q.empty()) q.pop(); node t; t.x = x; t.y = y; t.z = z; t.step = 0; q.push(t); while (!q.empty()){ t = q.front(); q.pop(); if (t.x==a && t.y==b && t.z==c) return t.step; for (int i=0; i<6; ++i){ node p; p.x = t.x+dir[i][0]; p.y = t.y+dir[i][1]; p.z = t.z+dir[i][2]; p.step = t.step+1; if (check(p.x, p.y, p.z) && !mp[p.x][p.y][p.z] && !vis[p.x][p.y][p.z]){ q.push(p); vis[p.x][p.y][p.z] = true; } } } return -1; } int main(){ int T; scanf("%d", &T); while (T--){ scanf("%d%d%d%d", &a, &b, &c, &d); for (int i=1; i<=a; ++i) for (int j=1; j<=b; ++j) for (int k=1; k<=c; ++k) scanf("%d", &mp[i][j][k]); memset(vis, false, sizeof(vis)); int ans = bfs(1, 1, 1); //cout << ans << endl; if (ans > d) ans = -1; printf("%d\n", ans); } return 0; }