欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

各种迷迷迷宫问题 深搜dfs和广搜bfs做法

程序员文章站 2023-12-27 14:25:28
...

三分钟热度又回来了

谈到迷宫问题就得提到解决迷宫问题的常见做法,bfs和dfs
各种迷迷迷宫问题 深搜dfs和广搜bfs做法在处理迷宫问题时,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列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。
输入
第一行是两个整数,R和C,代表迷宫的长和宽。( 1<= R,C <= 40)
接下来是R行,每行C个字符,代表整个迷宫。
空地格子用’.‘表示,有障碍物的格子用’#‘表示。
迷宫左上角和右下角都是’.’。
输出
输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。
样例输入

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;
}

迷宫是走不完的,下次有时间再补,以后一定写注释

各种迷迷迷宫问题 深搜dfs和广搜bfs做法

相关标签: 学习记录

上一篇:

下一篇: