AcWing 1096. 地牢大师

1096. 地牢大师 - AcWing题库

三维数组bfs

知识：数组模拟队列，bfs。

1. 结构体定义时，字母顺序颠倒。

2. 数组越界，数组开小了。

#include 
#include 
#include 
#include 

using namespace std;

const int N = 150;

int ans;
int l, n, m;
char road[N][N][N];
bool vis[N][N][N];
int dz[6] = {0, 0, 0, 0, 1, -1};
int dx[6] = {1, 0, -1, 0, 0, 0};
int dy[6] = {0, 1, 0, -1, 0 ,0};

struct Dat
{
	int z, x, y, s;
}q[1000000];

bool check(int zz, int xx, int yy)
{
	return zz >= 0 && zz < l && xx >= 0 && xx < n && yy >= 0 && yy < m
	&& road[zz][xx][yy] != '#' && !vis[zz][xx][yy];
}

int bfs(int a, int b, int c)
{
	int hh = 0, tt = 0;
	q[0] = {a, b, c, 0};
	
	
	while (hh <= tt)
	{
		auto t = q[hh ++ ];
		
		if (road[t.z][t.x][t.y] == 'E') return t.s;
		for (int i = 0; i < 6; i ++ )
		{
			int zz = t.z + dz[i];
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			if (check(zz, xx, yy))
			{
				vis[zz][xx][yy] = true;
				q[++ tt] = {zz, xx, yy, t.s + 1};
			}
		}
	}
	
	return 0;
}

int main()
{
	
con:
	while (scanf("%d%d%d", &l, &n, &m))
	{
		if (l == 0 && n == 0 && m == 0) return 0;
		
		memset(vis, 0, sizeof(vis));
		
		for (int i = 0; i < l; i ++ )
			for (int j = 0; j < n; j ++)
				scanf("%s", road[i][j]);
			
		for (int i = 0; i < l; i ++ )
			for (int j = 0; j < n; j ++ )
				for (int k = 0; k < m; k ++ )
					if (road[i][j][k] == 'S')
					{
						vis[i][j][k] = true;
						ans = bfs(i, j, k);
						if (ans) printf("Escaped in %d minute(s).n", ans);
						else puts("Trapped!");
						goto con;
					} 
			
	}
	return 0;
}