各种迷迷迷宫问题 深搜dfs和广搜bfs做法
三分钟热度又回来了
谈到迷宫问题就得提到解决迷宫问题的常见做法，bfs和dfs在处理迷宫问题时，dfs一般用来解决能不能的问题，即从x点能否到达y点，而bfs一般用来解决最少需求的问题，即从x点走到y点最少需要多少步。当然，很多情况下，用bfs和dfs都能解决上述两个问题，就看哪种方法效率高或者说你乐意用哪种方法。
成天想什么呢，效率最重要
bfs:
定义一个队列；
起始点加入队列；
while（队列不为空）{
取出队头结点；
if 它是所求解，跳出循环；
else 从它拓展出子结点，并加入队尾；
}
如果循环中找到了解，输出结果；
否则输出无解；
dfs:
bool check(参数) {
if(满足条件)
return ture;
return false;
}
void dfs(int step) {
if(到达边界){
输出或其他相关操作 //根据题意添加
return ;
}
if(越界 / 不合法的状态)
return;
for() {
if(满足check) {
修改操作; //根据题意判断是否执行该操作 **1**
标记;
dfs(step + 1);//继续下一步
(还原标记) //根据题意判断是否执行该操作 **2**
//如果加上（还原标记）就是 回溯法
}
}
}
例题1 走迷宫
描述
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
输入
第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用’.‘表示，有障碍物的格子用’#‘表示。
迷宫左上角和右下角都是’.’。
输出
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
样例输入
5 5
..###
#....
#.#.#
#.#.#
#.#..
样例输出
9
#include<iostream>
int MinStep = 1e8;
int n, m;
char a[505][505];
void dfs(int x, int y, int step) {
int tx, ty;
a[x][y] = '#';
int next[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
if(x == n && y == m) {
if(step < MinStep) {
MinStep = step;
}
return ;
}
for(int i = 0; i < 4; ++i) {
tx = x + next[i][0];
ty = y + next[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty] !='#'){
dfs(tx, ty, step+1);
a[tx][ty] = '.';
}
}
return ;
}
using namespace std;
int main() {
cin>>n>>m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin>>a[i][j];
}
}
dfs(1, 1, 1);
cout<<MinStep<<"\n";
return 0;
}
例题2 迷宫
迷宫
描述
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
输入
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
样例输入
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
样例输出
YES
NO
#include<iostream>
using namespace std;
bool judge;
int p, q, r, c, n, m;
char a[505][505];
void dfs(int x, int y) {
int tx, ty;
a[x][y] = '#';
int next[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
if(x == r && y == c) {
judge = true;
return ;
}
for(int i = 0; i < 4; ++i) {
tx = x + next[i][0];
ty = y + next[i][1];
if(tx>=0&&tx<n&&ty>=0&&ty<n&&a[tx][ty] !='#'){
dfs(tx,ty);
}
}
}
int main() {
cin>>m;
while(m--) {
cin>>n;
judge = false;
for(int i = 0; i < n; ++i) {
scanf("%s",a[i]);
}
cin>>p>>q>>r>>c;
if(a[p][q] == '#' || a[r][c] == '#') {
puts("NO");
continue;
}
dfs(p,q);
if(judge) puts("YES");
else puts("NO");
}
return 0;
}
例题3 走出迷宫
走出迷宫
题目描述
小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。
小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。
障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；
小明想要知道，现在他能否从起点走到终点。
输入描述:
本题包含多组数据。
每组数据先输入两个数字N,M
接下来N行，每行M个字符，表示地图的状态。
数据范围：
2<=N,M<=500
保证有一个起点S，同时保证有一个终点E.
输出描述:
每组数据输出一行，如果小明能够从起点走到终点，那么输出Yes，否则输出No
示例1
输入
3 3
S..
..E
...
3 3
S##
###
##E
输出
Yes
No
bfs版本????
#include<iostream>
#include<cstring>
#include<queue>
#include<utility>
using namespace std;
#define se second
typedef pair<int,int> pii;
#define fi first
const int N = 505;
char a[N][N];
int n, m;
int fx[] = {0,0,1,-1};
int fy[] = {1,-1,0,0};
int vis[N][N];
int sx, sy, ex, ey, mx, my, kx, ky;
bool check(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != '#' && !vis[x][y];
}
void bfs() {
queue<pii> q;
q.push(make_pair(sx, sy));
vis[sx][sy] = 1;
while(!q.empty()) {
pii now = q.front(); q.pop();
for(int i = 0; i < 4; i++) {
int dx = fx[i] + now.fi, dy = fy[i] + now.se;
if(check(dx, dy)) {
vis[dx][dy] = 1;
q.push(make_pair(dx, dy));
}
}
}
}
int main() {
while(cin >> n >> m) {
memset(vis, 0, sizeof vis);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j){
cin>>a[i][j];
if(a[i][j] == 'S') sx = i, sy = j;
if(a[i][j] == 'E') ex = i, ey = j;
}
}
bfs();
if(vis[ex][ey]) puts("Yes");
else puts("No");
}
}
dfs版本????
#include<iostream>
bool judge;
int p, q, r, c, n, m;
char a[505][505];
void dfs(int x, int y) {
int tx, ty;
a[x][y] = '#';
int next[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
if(x == r && y == c) {
judge = true;
return ;
}
for(int i = 0; i < 4; ++i) {
tx = x + next[i][0];
ty = y + next[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty] !='#'){
dfs(tx,ty);
}
}
}
using namespace std;
int main() {
while(cin>>n>>m) {
judge = false;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin>>a[i][j];
if(a[i][j] == 'S') {
p = i;
q = j;
}
if(a[i][j] == 'E') {
r = i;
c = j;
}
}
}
dfs(p,q);
if(judge) puts("Yes");
else puts("No");
}
return 0;
}
例题4 迷宫
迷宫
题目描述
这是一个关于二维迷宫的题目。我们要从迷宫的起点 ‘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
输出
20
示例2
输入
6 6
WWWWWW
WEWS.W
W.WK.W
W.WD.W
W.W..W
WWWWWW
输出
-1
备注:
4 ≤ H, W≤ 500
‘S’, ‘E’, ‘K’, 'D’各出现恰好一次
迷宫的四周(最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是 ‘W’
PS：这题与上一题类似，不过迷宫里加了钥匙和门
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 505;
char a[N][N];
bool vis[N][N];
int n, m;
struct node{
int x, y, step;
}s , e;
int sx, sy, ex, ey, mx, my, kx, ky;
int bfs(int x1, int y1, int x2, int y2) {
int fx[] = {0,0,1,-1};
int fy[] = {1,-1,0,0};
s.x = x1, s.y = y1, e.x = x2, e.y = y2;
queue<node> q;
s.step = 0;
q.push(s);
vis[s.x][s.y] = 1;
while(!q.empty()) {
node t = q.front();
q.pop();
if(t.x == e.x && t.y == e.y) {
return t.step;
}
for(int i = 0; i < 4; ++i) {
s.x = t.x + fx[i];
s.y = t.y + fy[i];
if(s.x >= 1 &&s.x <= n && s.y >= 1 && s.y <= m && a[s.x][s.y] == '.'&& !vis[s.x][s.y]) {
vis[s.x][s.y] = 1;
s.step = t.step + 1;
q.push(s);
}
}
}
return -1;
}
int main() {
cin>>n>>m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin>>a[i][j];
if(a[i][j] == 'S') sx = i, sy = j;
if(a[i][j] == 'E') ex = i, ey = j;
if(a[i][j] == 'K') kx = i, ky = j;
if(a[i][j] == 'D') mx = i, my = j;
}
}
a[sx][sy] = '.', a[ex][ey] = '.', a[kx][ky] = '.';
int s = bfs(sx, sy, ex, ey);//直接到终点
memset(vis, 0, sizeof(vis));
int s1 = bfs(sx, sy, kx, ky);//找钥匙
memset(vis, 0, sizeof(vis));
a[mx][my] = '.';//找到了钥匙，就可以经过门
int s2 = bfs(kx, ky, mx, my);
memset(vis, 0, sizeof(vis));
int s3 = bfs(mx, my, ex, ey);//门到终点
if(s == -1) {
if(s1 == -1 || s2 == -1 || s3 == -1) puts("-1");
else cout<<s1+s2+s3<<"\n";
}
else cout<<min(s,(s1+s2+s3));
return 0;
}
例题5 after迷宫
after与迷宫
题目描述
after的算法书的遗落在一个叫做AIJ的迷宫中了，这个迷宫有N*M个房间，迷宫的入口为(1，1)，算法书遗落在(r，c)。迷宫中的房间有四种状态：空房间、无法进入的房间、有墨菲斯托存在的房间和有莉莉丝存在的房间。墨菲斯托会否定一切，而莉莉丝会诱惑人做一种叫做YK的活动。after是一个意志薄弱的人，他遇到了墨菲斯托和莉莉丝之后，便会变成眼神空洞的超级YK机器人。after每步可以从他当前的房间走至上下左右四个房间的其中一个房间。after害怕变成超级YK机器人，所以要尽快拿到算法书然后从入口逃离。问after最少需要走多少步才可以在不变成超级YK机器人的情况下从入口出发取回算法书并逃离迷宫？
输入描述:
第一行一个正整数T(T<=10)，表示共有T组数据。
对于每组数据，第一行四个正整数N，M，r，c(1<=N,M<=1000；1<=r<=N；1<=c<=M)。
接下来N行，每行M个字符，每个表示房间的状态，“.”表示空房间，“*”表示无法进入的房间，“F”表示有墨菲斯托存在的房间，“M”表示有莉莉丝存在的房间。
数据保证(1，1)为“.”。
输出描述:
对每组数据输出一行，即after最少需要走的步数。若after无法取回算法书，则输出“IMPOSSIBLE”(不带引号)。
示例1
输入
1
4 4 4 3
..**
*F..
*.*.
*M.F
输出
14
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1005;
char a[N][N];
char b[N][N];
bool vis[N][N];
int n, m;
struct node{
int x, y, step;
}s , e;
int r, c, mx, my, lx, ly;
int bfs(int x1, int y1, int x2, int y2) {
int fx[] = {0,0,1,-1};
int fy[] = {1,-1,0,0};
s.x = x1, s.y = y1, e.x = x2, e.y = y2;
queue<node> q;
s.step = 0;
q.push(s);
vis[s.x][s.y] = 1;
while(!q.empty()) {
node t = q.front();
q.pop();
if(t.x == e.x && t.y == e.y) {
return t.step;
}
for(int i = 0; i < 4; ++i) {
s.x = t.x + fx[i];
s.y = t.y + fy[i];
if(s.x >= 1 &&s.x <= n && s.y >= 1 && s.y <= m && b[s.x][s.y] == '.'&& !vis[s.x][s.y]) {
vis[s.x][s.y] = 1;
s.step = t.step + 1;
q.push(s);
}
}
}
return -1;
}
int main() {
int t;
cin>>t;
while(t--) {
cin>>n>>m>>r>>c;
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i) {
cin>>a[i] + 1;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(a[i][j] == 'F') b[i][j] = '.';
else b[i][j] = a[i][j];
}
}
int s = bfs(1, 1, r, c);
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(a[i][j] == 'M') b[i][j] = '.';
else b[i][j] = a[i][j];
}
}
int s1 = bfs(1, 1, r, c);
if(s == -1 && s1 == -1) {
puts("IMPOSSIBLE");
}else
if(s != -1 && s1 != -1) {
cout<<2 * min(s, s1)<<"\n";
}else cout<<2 * max(s, s1)<<"\n";
}
return 0;
}
迷宫是走不完的，下次有时间再补，以后一定写注释