题解 | #迷宫#

思路

• 总体思路是用BFS找最短路
• 由于拿到钥匙和没拿到钥匙两种状态对应的地图的形态不一样
  • 拿到钥匙时'D'可以通过,因此可以看作'.'
• 可以从分层图的角度考虑问题，第一层地图是没拿到钥匙的地图，第二层地图是拿到钥匙的地图。
• BFS遇到钥匙时，不仅要在第一层图的四个方向继续尝试搜索，还要将第二层地图的'K'位置放入队列中(相当于在第二层图上开始BFS，向队列中放入第一个节点的步骤)
  代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 510;
char g[MAX][MAX];
int dist[MAX][MAX][2];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int N, M;
struct Node {
	int x, y, z;
};

int solve() {
	int r, c;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (g[i][j] == 'S') {
				r = i, c = j;
			}
		}
	}
	
	memset(dist, -1, sizeof dist);
	
	queue<Node> q;
	q.push({r, c, 0});
	dist[r][c][0] = 0;
	
	int ans = -1;
	
	while (q.size()) {
		Node t = q.front();
		q.pop();
		
		if (g[t.x][t.y] == 'E') {
			ans = dist[t.x][t.y][t.z];
			break;
		}
		
		if (t.z == 0 && g[t.x][t.y] == 'K') {
			q.push({t.x, t.y, 1});
			dist[t.x][t.y][1] = dist[t.x][t.y][0];
		}
		
		for (int i = 0; i < 4; i++) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (dist[nx][ny][t.z] != -1 || g[nx][ny] == 'W' || t.z == 0 && g[t.x][t.y] == 'D') continue;
			q.push({nx, ny, t.z});
			dist[nx][ny][t.z] = dist[t.x][t.y][t.z] + 1;
		}
		
	}
	
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> N >> M;
	
	for (int i = 0; i < N; i++) cin >> g[i];
	
	int ans = solve();
	
	cout << ans << '\n';
	
	return 0;
}