2018年长沙理工大学第十三届程序设计竞赛 G 题：逃离迷宫

2018年长沙理工大学第十三届程序设计竞赛 G 题：逃离迷宫

思路：一开始从起点开始bfs搜，每搜到一把钥匙对应的k[i][j]的值更新为起点到该钥匙的距离，没有搜到的钥匙则为初始值-1。 然后再从终点开始一次bfs，搜到一把钥匙之后，先判断k[i][j]是否为-1，是的话说明无法从起点走到该钥匙位置，即通过这把钥匙从起点到终点是不可行的，那么继续向该位置的4个方向搜索，否的话说明从起点走到这把钥匙是有路的，且路长度存在k[i][j]里，那么k[i][j]+now.step就是从起点出发拿到这把钥匙到终点的最短路径，那么更新ans值为ans原本的值和k[i][j]+now.step 之间的最小值，然后继续向4个方向搜索

#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const int maxn = 5e2 + 5;
int G[maxn][maxn];
int v[maxn][maxn];
int k[maxn][maxn];
int px, py, ex, ey;
int ans;
int n, m;
int d[5][2] =
{0, 0,-1, 0,1, 0,0,-1,0, 1,
};
struct node
{int x, y, step;
};
bool judge(int x, int y)
{if (x < 0 || x >= n || y < 0 || y >= m || G[x][y] == 0 || v[x][y])return false;return true;
}
void bfs(int x, int y, int flag)
{memset(v,0,sizeof(v));queue <node> q;node tmp;tmp.x = x;tmp.y = y;tmp.step = 0;q.push(tmp);v[tmp.x][tmp.y] = 1;while (!q.empty()){node u = q.front(), w;q.pop();if (G[u.x][u.y] == 2){if (flag){if (k[u.x][u.y] != -1)ans = min(ans, k[u.x][u.y] + u.step);}else{k[u.x][u.y] = u.step;}}for (int i = 1; i < 5; i++){w.x = u.x + d[i][0];w.y = u.y + d[i][1];w.step = u.step + 1;if (judge(w.x, w.y)){q.push(w);v[w.x][w.y] = 1;}}}
}
int main()
{int t;cin >> t;while (t--){scanf("%d%d", &n, &m);char c;memset(k,-1,sizeof(k));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){scanf(" %c", &c);if (c == '#')G[i][j] = 0;else{G[i][j] = 1;if (c == 'P')px = i, py = j;else if (c == 'E')ex = i, ey = j;else if (c == 'K')G[i][j] = 2;}}}ans = INF;G[ex][ey] = 0;bfs(px, py, 0);G[ex][ey] = 1;bfs(ex, ey, 1);if (ans == INF)printf("No solutionn");elsecout << ans << endl;}
}