解题思路
三维bfs的模板题,没什么大坑,注意还是老话,走图题,千万千万别写dfs,会死的很惨很惨,MLE究极暴毙。。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 105; struct Node { int x, y, z, s; }; queue<Node> que; char mp[N][N][N]; bool vis[N][N][N]; int dx[] = { 1,-1,0,0,0,0 }; int dy[] = { 0,0,1,-1,0,0 }; int dz[] = { 0,0,0,0,1,-1 }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) for (int k = 1; k <= n; ++k) cin >> mp[i][j][k]; if (mp[n][n][n] == '*') puts("-1"); else { bool flag = false; queue<Node> que; que.push(Node{ 1,1,1,1 }); vis[1][1][1] = true; while (!que.empty()) { Node temp = que.front(); que.pop(); for (int i = 0; i < 6; ++i) { int xx = temp.x + dx[i], yy = temp.y + dy[i], zz = temp.z + dz[i]; if (xx<1 || yy<1 || zz<1 || xx>n || yy>n || zz>n || mp[xx][yy][zz] == '*' || vis[xx][yy][zz]) continue; que.push(Node{ xx,yy,zz,temp.s + 1 }); vis[xx][yy][zz] = true; if (xx == n && yy == n && zz == n) { printf("%d\n", temp.s + 1); flag = true; break; } } } if (!flag) puts("-1"); } return 0; }