链接：https://www.nowcoder.com/acm/contest/96/G
来源：牛客网
题目描述
给你一个n*m的图，地图上'.'代表可以走的地方，而'#'代表陷阱不能走，
'P'代表人物位置，'K'代表钥匙，'E'代表出口。人物一个，钥匙有多个，
（'K'的数量<=50)）,出口一个，每个位置可以向（上，下，左，右）四个
方向走一格，花费一个单位时间，现在你需要花费最少的时间拿到钥匙
然后从迷宫的出口出去(若没有钥匙，则不能进入迷宫出口所在的格子)。
'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，即我先从出口找钥匙，再从入口找钥匙，记录钥匙的位置，让步数累加，最后就是取最小值。
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #define N 550 5 #define mem(x) memset(x,0,sizeof(x)) 6 using namespace std; 7 char vis[N][N]; 8 int a[N][N],b[N][N],k[N][N]; 9 int dir[4][2]={1,0,-1,0,0,1,0,-1}; 10 int t; 11 int n,m; 12 struct Bu{ 13 int x,y,step; 14 }; 15 void bfs(int x,int y){ 16 mem(a); 17 queue<Bu> q; 18 Bu aa; 19 aa.x = x; 20 aa.y = y; 21 aa.step = 0; 22 q.push(aa); 23 a[x][y] = 1; 24 while(!q.empty()){ 25 aa = q.front(); 26 q.pop(); 27 for(int i=0;i<4;i++){ 28 int xx = aa.x + dir[i][0]; 29 int yy = aa.y + dir[i][1]; 30 if(xx>0&&xx<=n&&yy>0&&yy<=m&&vis[xx][yy]!='#'&&vis[xx][yy]!='E'&&a[xx][yy]==0){ 31 a[xx][yy] = 1; 32 if(vis[xx][yy]=='K'){ 33 k[xx][yy]+=aa.step + 1; 34 b[xx][yy]++; 35 } 36 Bu at; 37 at.x =xx; 38 at.y = yy; 39 at.step = aa.step+1; 40 q.push(at); 41 } 42 } 43 } 44 } 45 int main(){ 46 cin>>t; 47 while(t--){ 48 cin>>n>>m; 49 mem(vis); 50 mem(b); 51 mem(k); 52 int x1,y1,x2,y2,x3,y3; 53 for(int i=1;i<=n;i++) 54 for(int j=1;j<=m;j++){ 55 cin>>vis[i][j]; 56 if(vis[i][j]=='P') x1 = i,y1 = j; 57 if(vis[i][j]=='E') x2 = i,y2 = j; 58 } 59 bfs(x1,y1); 60 bfs(x2,y2); 61 int ans = 1e9; 62 for(int i=1;i<=n;i++){ 63 for(int j=1;j<=m;j++){ 64 if(b[i][j]==2){ 65 ans=min(ans,k[i][j]); 66 } 67 } 68 } 69 70 if(ans != 1e9) 71 cout << ans << endl; 72 else 73 cout << "No solution"<<endl; 74 } 75 return 0; 76 }