2018长沙理工大学第十三届

2018长沙理工大学第十三届

链接：
来源：牛客网

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

emmmmmbfs，卡了好久好久，最后发现四个方向弄错了，还有node  节点搞不明白，后来看了ac的代码算是a出来了。。。。

标记还是不太会

#include<iostream>
#include<queue>
#include<string.h>
#include<stdio.h>
using namespace std;
int q1,q2,endx,endy,m;
int a[505][505];
char map[505][505];
int visit[505][505][2];
int vist[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node
{int x;int y;int step;int k;
};
int dfs(int dx,int dy)
{memset(visit,0,sizeof(visit));queue <node> s1;node q;q.x=dx;q.y=dy;q.k=0;q.step=0;visit[dx][dy][0]=1;s1.push(q);while(!s1.empty()){node p=s1.front();s1.pop();// printf("%d %d n",p.x,p.y );if (map[p.x][p.y] == 'E') return p.step;for(int i=0;i<4;i++){node q;q.x=p.x+vist[i][0];q.y=p.y+vist[i][1];if(q.x<q1&&q.x>=0&&q.y<q2&&q.y>=0&&map[q.x][q.y]!='#'){if(map[q.x][q.y]=='K')  q.k=1;else q.k=p.k;if(visit[q.x][q.y][q.k])continue;visit[q.x][q.y][q.k]=1;if(map[q.x][q.y]=='E'&& !q.k){continue;}q.step=p.step+1;s1.push(q);}}}return -1;
}
int main() 
{int dx,dy;cin>>m;while(m--){cin>>q1>>q2;for(int i=0;i<q1;i++){for(int j=0;j<q2;j++){cin>>map[i][j];if(map[i][j]=='P'){dx=i;dy=j;	}}}int ans=-1;ans=dfs(dx,dy);if(ans == -1){cout<<"No solution"<<endl;}else{cout<<ans<<endl;}}return 0;
}