[BFS] 逃离迷宫 长沙理工大学校赛G

[BFS] 逃离迷宫 长沙理工大学校赛G

链接：
题目描述

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

输入
3
5 5
....P
##..E
K#...
##...
.....
5 5
P....
.....
..E..
.....
....K
5 5
P#..E
.#.#.
.#.#.
.#.#.
...#K

输出
No solution
12
No solution

//多个k：经过K的最短路 = 起点开始到k + 终点开始到k 的最短路之和最小
#include <bits/stdc++.h>
using namespace std;
int n, m;
char M[500][500], m1[500][500], m2[500][500];
int D[500][500], d1[500][500], d2[500][500];
int dirx[4] = {0, -1, 0, 1};
int diry[4] = { -1, 0, 1, 0};
struct weizhi
{int x, y;
} s, e;
queue<weizhi>sq, eq;
int main()
{int T;cin >> T;while ( T-- ){cin >> n >> m;for ( int i = 0; i < n; i++ )for ( int j = 0; j < m; j++ ){cin >> M[i][j];m1[i][j] = M[i][j], m2[i][j] = M[i][j];d1[i][j] = 1e9, d2[i][j] = 1e9, D[i][j] = 1e9;if ( M[i][j] == 'P' ) s.x = i, s.y = j, sq.push ( s );if ( M[i][j] == 'E' ) e.x = i, e.y = j, eq.push ( e );}  //复制两张相同的地图void sbfs ( weizhi );sbfs ( s ); //从起点开始广搜void ebfs ( weizhi );ebfs ( e ); //从终点开始int ans = 1e9;for ( int i = 0; i < n; i++ )for ( int j = 0; j < m; j++ ){if ( M[i][j] == 'K' )D[i][j] = d1[i][j] + d2[i][j];//总距离=起点到k + 终点到k ans = ( ans < D[i][j] ) ? ans : D[i][j];}if ( ans == 1e9 ) cout << "No solution" << endl;else cout << ans << endl;}return 0;
}
void sbfs ( weizhi s )
{d1[s.x][s.y] = 0;m1[s.x][s.y] = '#';while ( !sq.empty() ){weizhi now = sq.front();sq.pop();weizhi t;for ( int i = 0; i < 4; i++ ){t.x = now.x + dirx[i];t.y = now.y + diry[i];if ( t.x >= 0 && t.x < n && t.y >= 0 && t.y < m&& m1[t.x][t.y] != '#' && m1[t.x][t.y] != 'E' ){       //不能进入出口所在的格子m1[t.x][t.y] = '#';d1[t.x][t.y] = d1[now.x][now.y] + 1;sq.push ( t );}}}
}
void ebfs ( weizhi e )
{d2[e.x][e.y] = 0;m2[e.x][e.y] = '#';while ( !eq.empty() ){weizhi now = eq.front();eq.pop();weizhi t;for ( int i = 0; i < 4; i++ ){t.x = now.x + dirx[i];t.y = now.y + diry[i];if ( t.x >= 0 && t.x < n && t.y >= 0 && t.y < m&& m2[t.x][t.y] != '#' ){m2[t.x][t.y] = '#';d2[t.x][t.y] = d2[now.x][now.y] + 1;eq.push ( t );}}}
}