逃离迷宫bfs

链接：https://ac.nowcoder.com/acm/problem/15552
来源：牛客网

题目描述
给你一个n*m的图，地图上'.'代表可以走的地方，而'#'代表陷阱不能走，
'P'代表人物位置，'K'代表钥匙，'E'代表出口。人物一个，钥匙有多个，
（'K'的数量<=50)）,出口一个，每个位置可以向（上，下，左，右）四个
方向走一格，花费一个单位时间，现在你需要花费最少的时间拿到钥匙
然后从迷宫的出口出去(若没有钥匙，则不能进入迷宫出口所在的格子)。
输入描述:
第一行一个整数T(T <= 50)，代表数据的组数
接下来一行n,m(n<=500,m<=500),代表地图的行和列
接下来n行，每行一个长度为m的字符串，组成一个图。
输出描述:
如果可以出去，输出所花费的最少时间。
如果不能出去，输出一行"No solution"。
示例1
输入
复制
3
5 5
....P
##..E
K#...
##...
.....
5 5
P....
.....
..E..
.....
....K
5 5
P#..E
.#.#.
.#.#.
.#.#.
...#K
输出
复制
No solution
12
No solution
//就很标准的bfs找最短路，但这个钥匙有很多个，从人物找钥匙，再从出口找钥匙，开个数组存距离，最后min一下

//https://www.acwing.com/video/277/  
#include<bits/stdc++.h>
#define ll long long  
using namespace std;
const int N=520; 
#define ll long long
typedef pair<int,int>PII;
int n,m,pp,ji1,ji2,minn=2550; 
int d[N][N],kk[N][N];
char a[N][N];
void bfs1(int star1,int star2)
{
    ji1=0;ji2=0;
    memset(d,-1,sizeof d);
    memset(kk,-1,sizeof kk);
    d[star1][star2]=0;
    queue<PII>q;
    q.push({star1,star2});
    int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]=='.'&&d[x][y]==-1)
            {
                q.push({x,y});
                d[x][y]=d[t.first][t.second]+1;
            }
            if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]=='K'&&d[x][y]==-1)
            {
                d[x][y]=d[t.first][t.second]+1;
                kk[x][y]=d[x][y];
            }
        }
    }
    return ;
}
void bfs2(int ji1,int ji2)
{
    minn=2550;
    memset(d,-1,sizeof d);
    d[ji1][ji2]=0;
    queue<PII>q;
    q.push({ji1,ji2});
    int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]=='.'&&d[x][y]==-1)
            {
                q.push({x,y});
                d[x][y]=d[t.first][t.second]+1;
            }
            if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]=='K'&&d[x][y]==-1&&kk[x][y]!=-1)
            {
                d[x][y]=d[t.first][t.second]+1;
                kk[x][y]+=d[x][y];
                minn=min(minn,kk[x][y]);
           //     cout<<minn<<"   "<<kk[x][y]<<"   "<<x<<"  "<<y<<endl;
            }
        }
    }
    return ;
}
int main()
{    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>pp;
    while(pp--)
    {
        cin>>n>>m;
        int star1,star2,chu1,chu2;
        for(int i=0;i<n;i++)
            for(int k=0;k<m;k++)
            {
                cin>>a[i][k];
                if(a[i][k]=='P')
                {
                    star1=i;star2=k;
                }
                if(a[i][k]=='E') chu1=i,chu2=k; 
            }
        bfs1(star1,star2);
        bfs2(chu1,chu2);
        if(minn==2550)
        {
            cout<<"No solution"<<endl;
            continue;
        }
        cout<<minn<<endl;
    }
    return 0;
}