B-迷宫

107 阅读 0 评论 71 点赞

我是靠谱客的博主多情背包，这篇文章主要介绍B-迷宫，现在分享给大家，希望可以做个参考。

链接： https://www.nowcoder.net/acm/contest/68/B
来源：牛客网

题目描述

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

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

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

输入描述:

复制代码

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

输出描述:

复制代码

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

链接：https://www.nowcoder.net/acm/contest/68/B
来源：牛客网

示例1

输入

复制代码

1
2
3
4
5
4 12
WWWWWWWWWWWW
WE.W.S..W.KW
W..D..W....W
WWWWWWWWWWWW

输出

复制代码

1
20

示例2

输入

复制代码

1
2
3
4
5
6
7
6 6
WWWWWW
WEWS.W
W.WK.W
W.WD.W
W.W..W
WWWWWW

输出

复制代码

1
-1

题意：求S到E的最小步数，其中有门和钥匙的情况，分开bfs就可以了。

思路：分两种情况：首先不用门的直接S到E的最小步数，bfs求得ans1。然后需要门的时候，此时必然需要钥匙，先bfs求得S到K的最小步数ans2，然后以K为起点，bfs求得K到E的最小步数ans3，最后比较ans1和ans2+ans3的大小，输出最小的即可。都不存在则输出-1。

因本人太菜，写了3个bfs，其实都差不多，还请大神不要见怪。

复制代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
ll x,y,s;
};
char mp[550][550];
ll n,m,sx,sy,kx,ky,vis[550][550];
ll mv[4][2]={-1,0,0,1,1,0,0,-1};
ll bfs_E()
//bfs求直接S到E
{
memset(vis,0,sizeof(vis));
node now;
now.x=sx;
now.y=sy;
now.s=0;
queue<node>q;
q.push(now);
vis[now.x][now.y]=1;
while(!q.empty())
{
now=q.front();q.pop();
for(ll i=0;i<4;i++)
{
ll X=now.x+mv[i][0];
ll Y=now.y+mv[i][1];
if(X>=1&&X<=n&&Y>=1&&Y<=m&&vis[X][Y]==0&&mp[X][Y]!='W'&&mp[X][Y]!='D')
{
vis[X][Y]=1;
node nex;
nex.x=X;
nex.y=Y;
nex.s=now.s+1;
if(mp[nex.x][nex.y]=='E')return nex.s;
q.push(nex);
}
}
}
return -1;
}
ll bfs_K()
//bfs求S到K
{
memset(vis,0,sizeof(vis));
node now;
now.x=sx;
now.y=sy;
now.s=0;
queue<node>q;
q.push(now);
vis[now.x][now.y]=1;
while(!q.empty())
{
now=q.front();q.pop();
for(ll i=0;i<4;i++)
{
ll X=now.x+mv[i][0];
ll Y=now.y+mv[i][1];
if(X>=1&&X<=n&&Y>=1&&Y<=m&&vis[X][Y]==0&&mp[X][Y]!='W'&&mp[X][Y]!='D')
{
vis[X][Y]=1;
node nex;
nex.x=X;
nex.y=Y;
nex.s=now.s+1;
if(mp[nex.x][nex.y]=='K')
{
kx=nex.x;
ky=nex.y;
return nex.s;
}
q.push(nex);
}
}
}
return -1;
}
ll bfs_K_E()
//bfs求K到E
{
memset(vis,0,sizeof(vis));
node now;
now.x=kx;
now.y=ky;
now.s=0;
queue<node>q;
q.push(now);
vis[now.x][now.y]=1;
while(!q.empty())
{
now=q.front();q.pop();
for(ll i=0;i<4;i++)
{
ll X=now.x+mv[i][0];
ll Y=now.y+mv[i][1];
if(X>=1&&X<=n&&Y>=1&&Y<=m&&vis[X][Y]==0&&mp[X][Y]!='W')
{
vis[X][Y]=1;
node nex;
nex.x=X;
nex.y=Y;
nex.s=now.s+1;
if(mp[nex.x][nex.y]=='E')return nex.s;
q.push(nex);
}
}
}
return -1;
}
int main()
{
while(~scanf("%lld%lld",&n,&m))
{
for(ll i=1;i<=n;i++)
{
scanf("%s",mp[i]+1);
for(ll j=1;j<=m;j++)
{
if(mp[i][j]=='S')
{
sx=i;
sy=j;
}
}
}
ll ans1=-1,ans2=-1,ans3=-1;
ans1=bfs_E();
ans2=bfs_K();
if(ans2!=-1)
{
ans3=bfs_K_E();
}
if(ans1==-1)
{
if(ans2==-1)printf("-1n");
else
{
if(ans3==-1)printf("-1n");
else printf("%lldn",ans2+ans3);
}
}
else
{
if(ans2==-1)printf("%lldn",ans1);
else
{
if(ans3==-1)printf("%lldn",ans2);
else printf("%lldn",min(ans1,ans2+ans3));
}
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
ll x,y,s;
};
char mp[550][550];
ll n,m,sx,sy,kx,ky,vis[550][550];
ll mv[4][2]={-1,0,0,1,1,0,0,-1};
ll bfs_E()
//bfs求直接S到E
{
memset(vis,0,sizeof(vis));
node now;
now.x=sx;
now.y=sy;
now.s=0;
queue<node>q;
q.push(now);
vis[now.x][now.y]=1;
while(!q.empty())
{
now=q.front();q.pop();
for(ll i=0;i<4;i++)
{
ll X=now.x+mv[i][0];
ll Y=now.y+mv[i][1];
if(X>=1&&X<=n&&Y>=1&&Y<=m&&vis[X][Y]==0&&mp[X][Y]!='W'&&mp[X][Y]!='D')
{
vis[X][Y]=1;
node nex;
nex.x=X;
nex.y=Y;
nex.s=now.s+1;
if(mp[nex.x][nex.y]=='E')return nex.s;
q.push(nex);
}
}
}
return -1;
}
ll bfs_K()
//bfs求S到K
{
memset(vis,0,sizeof(vis));
node now;
now.x=sx;
now.y=sy;
now.s=0;
queue<node>q;
q.push(now);
vis[now.x][now.y]=1;
while(!q.empty())
{
now=q.front();q.pop();
for(ll i=0;i<4;i++)
{
ll X=now.x+mv[i][0];
ll Y=now.y+mv[i][1];
if(X>=1&&X<=n&&Y>=1&&Y<=m&&vis[X][Y]==0&&mp[X][Y]!='W'&&mp[X][Y]!='D')
{
vis[X][Y]=1;
node nex;
nex.x=X;
nex.y=Y;
nex.s=now.s+1;
if(mp[nex.x][nex.y]=='K')
{
kx=nex.x;
ky=nex.y;
return nex.s;
}
q.push(nex);
}
}
}
return -1;
}
ll bfs_K_E()
//bfs求K到E
{
memset(vis,0,sizeof(vis));
node now;
now.x=kx;
now.y=ky;
now.s=0;
queue<node>q;
q.push(now);
vis[now.x][now.y]=1;
while(!q.empty())
{
now=q.front();q.pop();
for(ll i=0;i<4;i++)
{
ll X=now.x+mv[i][0];
ll Y=now.y+mv[i][1];
if(X>=1&&X<=n&&Y>=1&&Y<=m&&vis[X][Y]==0&&mp[X][Y]!='W')
{
vis[X][Y]=1;
node nex;
nex.x=X;
nex.y=Y;
nex.s=now.s+1;
if(mp[nex.x][nex.y]=='E')return nex.s;
q.push(nex);
}
}
}
return -1;
}
int main()
{
while(~scanf("%lld%lld",&n,&m))
{
for(ll i=1;i<=n;i++)
{
scanf("%s",mp[i]+1);
for(ll j=1;j<=m;j++)
{
if(mp[i][j]=='S')
{
sx=i;
sy=j;
}
}
}
ll ans1=-1,ans2=-1,ans3=-1;
ans1=bfs_E();
ans2=bfs_K();
if(ans2!=-1)
{
ans3=bfs_K_E();
}
if(ans1==-1)
{
if(ans2==-1)printf("-1n");
else
{
if(ans3==-1)printf("-1n");
else printf("%lldn",ans2+ans3);
}
}
else
{
if(ans2==-1)printf("%lldn",ans1);
else
{
if(ans3==-1)printf("%lldn",ans2);
else printf("%lldn",min(ans1,ans2+ans3));
}
}
}
return 0;
}