牛客网——迷宫

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

这是一个关于二维迷宫的题目。我们要从迷宫的起点 'S' 走到终点 'E'，每一步我们只能选择上下左右四个方向中的一个前进一格。 'W' 代表墙壁，是不能进入的位置，除了墙壁以外的地方都可以走。迷宫内的 'D' 代表一道上锁的门，只有在持有钥匙的时候才能进入。而 'K' 则代表了钥匙，只要进入这一格，就会自动地拿到钥匙。最后 '.' 则是代表空无一物的地方，欢迎自在的游荡。

本题的迷宫中，起点、终点、门跟钥匙这四个特殊物件，每一个恰好会出现一次。而且，此迷宫的四周 (最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是墙壁。

请问，从起点到终点，最少要走几步呢？

输入描述:

输入的第一行有两个正整数H, W，分别代表迷宫的长跟宽。
接下来的H行代表迷宫，每行有一个长度恰为W的字串，此字串只包含`'S'`, `'E'`, `'W'`, `'D '`, `'K'`, `'.'`这几种字元。

输出描述:

请在一行中输出一个整数代表答案，如果无法从起点走到终点，请输出-1。

示例1

输入

复制4 12 WWWWWWWWWWWW WE.W.S..W.KW W..D..W....W WWWWWWWWWWWW

4 12
WWWWWWWWWWWW
WE.W.S..W.KW
W..D..W....W
WWWWWWWWWWWW

输出

复制20

20

示例2

输入

复制6 6 WWWWWW WEWS.W W.WK.W W.WD.W W.W..W WWWWWW

6 6
WWWWWW
WEWS.W
W.WK.W
W.WD.W
W.W..W
WWWWWW

输出

复制-1

-1

备注:

4 ≤ H, W≤ 500
'S', 'E', 'K', 'D'各出现恰好一次
迷宫的四周(最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是 'W'

有两种情况：1.起点->终点 2.起点->钥匙->门->终点
注意第一种情况可以走钥匙的格子，不能走门的格子。
 

#include <stdio.h>
#include <cstring> 
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxv=600;
int n,m;
char G[maxv][maxv];
bool vis[maxv][maxv]={false};
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
struct Node{
	int x,y;
	int step;
}node;
bool text(int x,int y){
	if(x<0||x>=n||y<0||y>=m){
		return false;
	}
	if(vis[x][y]==true){
		return false;
	}
	if(G[x][y]=='W'){
		return false;
	}
	if(G[x][y]=='D'){
		return false;
	}
	return true;
}
int BFS(int s_x,int s_y,int e_x,int e_y){
	queue<Node> q;
	node.x=s_x;
	node.y=s_y;
	node.step=0;
	q.push(node);
	vis[s_x][s_y]=true;
	while(!q.empty()){
		Node top=q.front();
		q.pop();
		if(top.x==e_x&&top.y==e_y){
			return top.step;
		}
		int new_x;int new_y;
		for(int i=0;i<4;i++){
			new_x=top.x+X[i];
			new_y=top.y+Y[i];
			if(text(new_x,new_y)){
				node.x=new_x;
				node.y=new_y;
				node.step=top.step+1;
				q.push(node);
				vis[new_x][new_y]=true;
			}
		}
	}
	return -1;
}
int main(){
		int s_x=-1,s_y=-1;
		int e_x=-1,e_y=-1;
		int  key_x=-1,key_y=-1;
		int door_x=-1,door_y=-1;
		
		scanf("%d%d",&n,&m);
		
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>G[i][j];
				if(G[i][j]=='S'){
					s_x=i;
					s_y=j;
				}
				if(G[i][j]=='E'){
					e_x=i;
					e_y=j;
				}
				if(G[i][j]=='K'){
					key_x=i;
					key_y=j;
				}
				if(G[i][j]=='D'){
					door_x=i;
					door_y=j;
				}
			}
		}
		memset(vis,0,sizeof(vis));
		int ans=BFS(s_x,s_y,e_x,e_y);//直接到达 (可以拿钥匙)
		
		memset(vis,0,sizeof(vis));
		int ans1=BFS(s_x,s_y,key_x,key_y);//起点到钥匙 
		memset(vis,0,sizeof(vis));
		G[door_x][door_y]='.';//执行ans3时，要将'D'改变成'.' 
		int ans2=BFS(key_x,key_y,door_x,door_y);//钥匙到锁 
		memset(vis,0,sizeof(vis));
		int ans3=BFS(door_x,door_y,e_x,e_y);//锁到终点 
		if(ans==-1){
			if(ans1==-1||ans2==-1||ans3==-1){
				printf("-1\n");
			}else{
				printf("%d\n",ans1+ans2+ans3);
			}
		}else{
			int sum=min(ans,ans1+ans2+ans3);
			printf("%d\n",sum);
		}
		
	return 0;
}