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 solution
");
        else
            cout << ans << endl;
    }
}