长沙理工大学第13届程序设计大赛 G.逃离迷宫

长沙理工大学第13届程序设计大赛 G.逃离迷宫

题意：给你一个起点，一个终点，在地图中分布着一些钥匙，你需要先拿到钥匙，然后采取前往终点处，问需要通关多少步能完成任务。

题解：题目挺简单的，唯一坑点在于在没有找到钥匙之前，人是不能够穿过终点的，就相当于终点是障碍物。由于题目的要求，这就转化成了求2遍bfs，先从起点出发，搜索能够取到的钥匙，然后再从终点出发，搜索能够取到的钥匙。最后依次枚举所有的钥匙，如果存在正向和反向都能取到的钥匙，那就记录最小值就行啦。
还有最后很重要的一点，在多组输入的时候一定要记得清空vector又因为是这个原因找了1小时bug

下面是代码：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int>pii;
const int maxn = 505;
int dir[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
int d[2][maxn][maxn];
int t, n, m;
char S[maxn][maxn];
vector<pii>key;
pii beginpos, endpos;
void init() {for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(S[i][j] == 'P') beginpos = pii(i, j);else if(S[i][j] == 'E') endpos = pii(i, j);else if(S[i][j] == 'K') key.push_back(pii(i, j));}}memset(d, inf, sizeof(d));
}
void bfs(pii pos, int id) {queue<pii>q;q.push(pos);d[id][pos.first][pos.second] = 0;while(!q.empty()) {pos = q.front();q.pop();int x = pos.first;int y = pos.second;for(int k = 0; k < 4; k++) {int nx = x + dir[k][0];int ny = y + dir[k][1];if(nx < 1 || ny < 1 || nx > n || ny > m || S[nx][ny] == '#') continue;if(id == 0 && S[nx][ny] == 'E') continue;if(d[id][nx][ny] > d[id][x][y] + 1) {d[id][nx][ny] = d[id][x][y] + 1;q.push(pii(nx, ny));}}}
}
int solve() {key.clear();init();bfs(beginpos, 0);bfs(endpos, 1);int MIN = inf;for(int i = 0; i < key.size(); i++) {int x = key[i].first;int y = key[i].second;MIN = min(MIN, d[0][x][y] + d[1][x][y]);}return MIN;
}
int main() {scanf("%d", &t);while(t--) {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%s", S[i] + 1);int ans = solve();if(ans == inf) {printf("No solutionn");} else {printf("%dn", ans);}}return 0;
}