摘要
Title: 844. 走迷宫
Tag: BFS
Memory Limit: 64 MB
Time Limit: 1000 ms

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

844. 走迷宫

题意

思路

代码