Powered by:NEFU AB-IN

Link

844. 走迷宫

• 题意

  给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
  最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
  请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。
  数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

• 思路

  BFS板子题, 两种写法！

  • 第一种写法
    • 正常写法，就是每个点只遍历一遍，所以用个vis数组保证不走回头路
    • 标记状态
      • 在入队后进行标记，因为第一次搜到的点才是最短距离，需要标记，确保以后如果搜到这个点的话，不让它进队
  • 第二种写法
    • 因为bfs就相当于w等于1的最短路问题，可以按照dijkstra的板子来写
    • 其实也就相当于双端队列广搜的写法，只不过这里的路径只有1，而双端队列广搜的路径有0也有1

• 代码

  第一种写法

  '''
  Author: NEFU AB-IN
  Date: 2022-02-11 16:24:27
  FilePath: \Acwing\844\844.py
  LastEditTime: 2023-02-27 21:31:02
  '''
  
  from collections import deque
  
  N = 110
  g = []
  vis = [[0] * N for _ in range(N)]
  
  dx = [-1, 0, 1, 0]
  dy = [0, 1, 0, -1]
  
  
  def bfs(x, y):
      q = deque()
      q.appendleft((x, y, 0))
      vis[x][y] = 1
      while len(q):
          t = q.pop()
          (x, y, cnt) = t # 多变量与元组进行挨个赋值
          if x == n - 1 and y == m - 1:
              return cnt
          for i in range(4):
              a = x + dx[i]
              b = y + dy[i]
              if a >= 0 and a < n and b >= 0 and b < m and vis[a][b] == 0 and g[
                      a][b] == 0:
                  q.appendleft((a, b, cnt + 1))
                  vis[a][b] = 1
  
  
  n, m = map(int, input().split())
  for i in range(n):
      g.append(list(map(int, input().split())))
  
  print(bfs(0, 0))
  

  ---

  第二种写法

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-04-06 23:19:14
  * @FilePath: \Acwing\844\844.cpp
  * @LastEditTime: 2023-04-06 23:24:55
  */
  #include <algorithm>
  #include <cstring>
  #include <iostream>
  #include <queue>
  
  using namespace std;
  
  const int N = 110;
  
  struct sa
  {
      int x, y;
  };
  
  int n, m;
  int dist[N][N], g[N][N];
  int dx[4] = {1, -1, 0, 0};
  int dy[4] = {0, 0, 1, -1};
  
  void print()
  {
      for (int i = 1; i <= n; ++i)
      {
          for (int j = 1; j <= m; ++j)
          {
              cout << dist[i][j] << " ";
          }
          cout << '\n';
      }
  }
  
  int bfs()
  {
      queue<sa> q;
      q.push({1, 1});
      memset(dist, 0x3f, sizeof dist);
      dist[1][1] = 0;
  
      while (q.size())
      {
          auto t = q.front();
          q.pop();
          if(st[t.x][t.y]) 
              continue;
          st[t.x][t.y] = 1;
        
          for (int i = 0; i < 4; ++i)
          {
              int x = t.x + dx[i];
              int y = t.y + dy[i];
              if (x < 1 || x > n || y < 1 || y > m || g[x][y] == 1)
                  continue;
              if (dist[x][y] > dist[t.x][t.y] + 1)
              {
                  dist[x][y] = dist[t.x][t.y] + 1;
                  // print();
                  if (x == n && y == m)
                  {
                      return dist[x][y];
                  }
                  q.push({x, y});
              }
          }
      }
  }
  
  int main()
  {
      cin >> n >> m;
      for (int i = 1; i <= n; ++i)
      {
          for (int j = 1; j <= m; ++j)
          {
              cin >> g[i][j];
          }
      }
      cout << bfs();
      return 0;
  }