带门和钥匙的迷宫
迷宫
https://ac.nowcoder.com/acm/problem/15136
迷宫
题意:
有一个二维迷宫，需要从S点走到E点，每一步之能选择上下左右四个方向前进一格。W代表墙壁，D代表一扇门，需持有钥匙才能通过，K代表钥匙，经过该点钥匙就会自动进入你的口袋，'.'代表是空的，可以走。
问你从起点到终点最少需要几步？
思路：
因为问的是最短路的长度，所以是bfs题
但是这个题介入了钥匙和门这俩恶心的玩意就比较坑！
你不可能通过计算一次bfs就得到答案，因为bfs时每个点只能走一次，用完这个点就扔掉了，不会走回头路，这就会导致一种情况：如样例一
4 12 WWWWWWWWWWWW WE.W.S..W.KW W..D..W....W WWWWWWWWWWWW
第三个就踩到门D了，这个时候你没有钥匙，就会进不去，最后就不能到终点。而这个地方的正解是你先去K处拿到钥匙，再去开门到终点，你会发现会重复走，所以就不是一个bfs能解决的了的事！
我们知道要想到达终点分两种情况，一是不进门去走，看看能不能走到终点，另一种是走门再到终点。
而走门又分为两种情况，一是钥匙会在路上捡到，不用刻意去捡，另一种是得先多跑几步找钥匙，再去开门。总的来说，走门得分两步，先bfs从起点到钥匙处，再bfs从钥匙到门，这样得到的肯定是最小步数。
所以，综上所述，解决这个问题可以分两种情况
- 将门的位置当成墙，再用bfs去找
- 先来一步从起点到钥匙的bfs，再来一步从钥匙到门到bfs，再来一步门到终点的bfs，最后三步相加
假设我们bfs没找到最短路时返回的是无穷大，那么如果情况1返回无穷大并且情况二中至少有一个出现无穷大，就说明到不了终点，返回-1
剩下的情况就输出情况一和情况二的最小值
好看一点的AC码
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 7
#define endl '\n'
#define mod 1e9+7;
typedef long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int h, w, x1, yy1, ans, key,xk, yk ,xd, yd;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool vis[505][505];
char tr[505][505];
struct ran{
int x, y, step;
};
queue<ran>q;
ran over[5];//用来记录点的位置
bool judge(int x, int y){
if(x > h || x < 1 || y > w || y < 1)return false;
else if(vis[x][y])return false;
else if(tr[x][y] == 'W' || tr[x][y] == 'D')return false;
else return true;
}
int bfs(int xx, int yy){
ran now, next;
now.x = xx;now.y = yy;now.step = 0;
q.push(now);
vis[xx][yy] = 1;
while (!q.empty()) {
now = q.front();q.pop();
//一定要把结束的情况放在外面判断鸭，我之前做了一个判能否走出迷宫的题把这个放在for外面wa了，放里面ac了，所以我写的时候就放里面了，结果wa了，呜呜，写了好长时间呢，后来换了个方法写（也就是这个代码），发现和第一遍一样还是每个步数有的差1有的不差1 ，就发现原来是这个地方出了问题！淦
if(now.x == x1 && now.y == yy1){
return now.step;
}
for(int i = 0; i < 4; ++i){
next.x = now.x + dx[i];next.y = now.y + dy[i];
if(!judge(next.x, next.y))continue;
//cout<<now.x<<' '<<now.y<<" -> "<<next.x<<' '<<next.y<<endl;
vis[next.x][next.y] = 1;
next.step = now.step + 1;
q.push(next);
}
}
return inf;
}
void init(){//初始化
memset(vis, 0, sizeof(vis));
while (!q.empty()) {
q.pop();
}
}
int main(){
cin>>h>>w;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j){
scanf(" %c",&tr[i][j]);
if(tr[i][j] == 'S'){//起点
over[1].x = i;over[1].y = j;
}
if(tr[i][j] == 'K'){//钥匙
over[2].x = i;over[2].y = j;
}
if(tr[i][j] == 'D'){//门
over[3].x = i;over[3].y = j;
}
if(tr[i][j] == 'E'){//终点
over[4].x = i;over[4].y = j;
}
}
init();//从起点到终点
x1 = over[4].x;yy1 = over[4].y;
int a = bfs(over[1].x, over[1].y);
init();//从起点到钥匙
x1 = over[2].x;yy1 = over[2].y;
int b = bfs(over[1].x, over[1].y);
init();//从钥匙到门
x1 = over[3].x;yy1 = over[3].y;
tr[over[3].x][over[3].y] = '.';//注意要及时把门给拆了！
int c = bfs(over[2].x, over[2].y);
init();//从门到终点
x1 = over[4].x; yy1 = over[4].y;
int d = bfs(over[3].x, over[3].y);
if(a == inf && (b == inf || c == inf || d == inf))
cout<<-1<<endl;
else cout<<min(a, b + c + d)<<endl;
return 0;
}
/*
5 5
WWWWW
WS.KW
WW.WW
WD.EW
WWWWW
*/
在贴一份我第一遍写的奇丑无比的代码(╥﹏╥)
虽然丑了点，但是在我顿悟后改了一下，也ac了W(''0'')W
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 7
#define endl '\n'
#define mod 1e9+7;
typedef long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int h, w, x1, yy1, ans, key,xk, yk ,xd, yd;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool vis[505][505];
char tr[505][505];
struct ran{
int x, y, step;
};
queue<ran>q;
bool judge(int x, int y){
if(x > h || x < 1 || y > w || y < 1)return false;
else if(vis[x][y])return false;
else if(tr[x][y] == 'W')return false;
//else if(tr[x][y] == 'D' && key == 0)return false;
else return true;
}
int bfs1(){//不走门直接走
ran now, next;
now.x = x1;now.y = yy1;now.step = 0;
vis[x1][yy1] = 1;
q.push(now);
while (!q.empty()) {
now = q.front();q.pop();
if(tr[now.x][now.y] == 'E'){
ans = now.step;
return ans;
//cout<<"到此为止！\n";
}
for(int i = 0; i < 4; ++i){
next.x = now.x + dx[i];next.y = now.y + dy[i];
if(!judge(next.x, next.y))continue;
if(tr[next.x][next.y] == 'D')continue;
//if(tr[next.x][next.y] == 'K')key = 1;
//cout<<now.x<<' '<<now.y<<" -> "<<next.x<<' '<<next.y<<endl;
vis[next.x][next.y] = 1;
next.step = now.step + 1;
q.push(next);
}
}
return inf;
}
int bfs2(){//从起点去拿钥匙的距离
while (!q.empty()) {
q.pop();
}
memset(vis, 0, sizeof(vis));
ran now, next;
now.x = x1; now.y = yy1; now.step = 0;
vis[x1][yy1] = 1;
q.push(now);
while (!q.empty()) {
now = q.front();q.pop();
if(tr[now.x][now.y] == 'K'){
ans = now.step;
return ans;
}
for(int i = 0; i < 4; ++i){
next.x = now.x + dx[i];
next.y = now.y + dy[i];
if(!judge(next.x, next.y))continue;
if(tr[next.x][next.y] == 'D')continue;
// if(tr[next.x][next.y] == 'K')key = 1;
next.step = now.step + 1;
vis[next.x][next.y] = 1;
q.push(next);
}
}
return inf;
}
int bfs3(){//从钥匙到门
while (!q.empty()) {
q.pop();
}
memset(vis, 0, sizeof(vis));
ran now, next;
now.x = xk; now.y = yk; now.step = 0;
vis[xk][yk] = 1;
q.push(now);
while (!q.empty()) {
now = q.front();q.pop();
if(tr[now.x][now.y] == 'D'){
ans = now.step;
//cout<<"到此为止！\n";
return ans;
}
for(int i = 0; i < 4; ++i){
next.x = now.x + dx[i];
next.y = now.y + dy[i];
if(!judge(next.x, next.y))continue;
//if(tr[next.x][next.y] == 'D')continue;
// if(tr[next.x][next.y] == 'K')key = 1;
//cout<<now.x<<' '<<now.y<<" -> "<<next.x<<' '<<next.y<<endl;
next.step = now.step + 1;
vis[next.x][next.y] = 1;
q.push(next);
}
}
return inf;
}
int bfs4(){//从门到终点
while (!q.empty()) {
q.pop();
}
memset(vis, 0, sizeof(vis));
ran now, next;
now.x = xd; now.y = yd; now.step = 0;
vis[xd][yd] = 1;
q.push(now);
while (!q.empty()) {
now = q.front();q.pop();
if(tr[now.x][now.y] == 'E'){
ans = now.step;
return ans;
}
for(int i = 0; i < 4; ++i){
next.x = now.x + dx[i];
next.y = now.y + dy[i];
if(!judge(next.x, next.y))continue;
//if(tr[next.x][next.y] == 'D')continue;
// if(tr[next.x][next.y] == 'K')key = 1;
next.step = now.step + 1;
vis[next.x][next.y] = 1;
q.push(next);
}
}
return inf;
}
int main(){
cin>>h>>w;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j){
scanf(" %c",&tr[i][j]);
if(tr[i][j] == 'S'){
x1 = i;yy1 = j;
tr[i][j] = '.';
}
if(tr[i][j] == 'K'){
xk = i;yk = j;
}
if(tr[i][j] == 'D'){
xd = i;yd = j;
}
}
//bfs3();
int a = bfs1();
int b = bfs2();
int c = bfs3();
int d = bfs4();
//cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
if(a == inf && (b == inf || c == inf || d == inf))
cout<<-1<<endl;
else
cout<<min(a,b + c + d)<<endl;
return 0;
}
/*
5 5
WWWWW
WS.KW
WW.WW
WD.EW
WWWWW
*/
