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

题目描述

给你一个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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <cmath>
 8 #include <queue>
 9 using namespace std;
10 #define  pi acos(-1.0)
11 typedef long long ll;
12 const int N =500+100;
13 int n,m,T;
14 char s[N][N];
15 int ex,ey;
16 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
17 bool check(int x,int y){
18     if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]!='#')//A,B都是可以再次走的，说明找到钥匙后还可以在走回去 
19     return true;
20     return false;
21 }
22 struct Node{
23     int x,y,step,key;
24     Node(){}
25     Node (int x,int y,int step,int key):x(x),y(y),step(step),key(key){}
26 }ss;
27 int bfs(Node nod){
28     queue<Node>Q;
29     Q.push(nod);
30     while(!Q.empty()){
31         Node tmp = Q.front();
32         Q.pop();
33         if(tmp.x==ex&&tmp.y==ey&&tmp.key==1){
34             return tmp.step;
35         }
36         for(int i=0;i<4;i++){
37             int x=tmp.x+dir[i][0];
38             int y=tmp.y+dir[i][1];
39             if(check(x,y)){
40                 if(tmp.key==0){//找到钥匙前变为A 
41                  //没有A，避免重复。 
42                     if(s[x][y]=='E') continue;//好没有钥匙，continue 
43                     if(s[x][y]=='.') {
44                         s[x][y]='A';
45                         Q.push(Node(x,y,tmp.step+1,0));
46                     }
47                     if(s[x][y]=='K'){
48                         s[x][y]='B';//找到钥匙了，变为B 
49                             Q.push(Node(x,y,tmp.step+1,1));
50                     }
51                 }
52                 else{
53                     if(s[x][y]!='B'){//找到钥匙后变为B 
54                         s[x][y]='B';
55                         Q.push(Node(x,y,tmp.step+1,1));
56                     }
57                 }
58             }
59         }
60     }
61     return -1;
62 }
63 int main()
64 {
65     scanf("%d",&T);
66     while(T--)
67     {    
68         scanf("%d%d",&n,&m);
69         for(int i=0;i<n;i++)
70         {
71             for(int j=0;j<m;j++){
72                 cin>>s[i][j];
73                 if(s[i][j]=='P'){
74                     ss.x=i,ss.y=j,ss.step=0;
75                 }
76                 if(s[i][j]=='E'){
77                     ex=i,ey=j;
78                 }
79             }
80         }
81         int ans=bfs(ss);
82         if(ans==-1){
83             printf("No solution
");
84         }
85         else{
86             printf("%d
",ans);
87         }
88     }
89     return 0;
90 }