解题思路

三维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;
}