BFS模板题 | 王同学的Blog

https://www.acwing.com/problem/content/846/

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 00 或 11，其中 00 表示可以走的路，11 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。

数据保证 (1,1)(1,1) 处和 (n,m)) 处的数字为 00，且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（00 或 11），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动右下角的最少移动次数

数据范围

1 <= n, m <= 100

输入样例:

输入样例

8

AC代码

#include <iostream>
#include <algorithm> //pair<int, int>
#include <cstring>   //memset(d, -1, sizeof d)
using namespace std;

const int N = 110;

int n, m;
int g[N][N];    //用来存迷宫具体的数值
int d[N][N];    //用来存各点到起点的距离
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //方向偏移量
pair<int, int> q[N*N]; //用数组来模拟队列, 数组的类型是int型二元组存坐标              

int bfs()
{
    int hh=0, tt=0;   //hh是队头, tt是队尾, 初始的时候都为0, hh==tt, 此时队为空
    q[0] = {0, 0};    //把起点(0, 0)入队, q数组是pair类型的队列
    memset(d, -1, sizeof d);//memset函数,<cstring>, memset(数组名, 把内容都置为-1, 数组大小)
                            //d数组是到起点的距离
    d[0][0] = 0;        //(0, 0)点到起点的距距离为0 
    while(hh <= tt)     //当队列不为空时
    {
        pair<int, int> t = q[hh++];//定义一个二元组变量t, 把队头给t, 准备启动
        for(int i = 0; i < 4; i++)      //依次遍历t的4个方向
        {
            int x = t.first + dx[i], y = t.second + dy[i];  //定义x, y 作为t的下一个坐标, 预备坐标
            if(x>=0 && x<n && y>=0 && y<m && g[x][y]==0 && d[x][y]==-1) // 如果x,y满足不撞边界, 
                                                                        //不撞墙, 和不走重复的路的条件
            {
                d[x][y] = d[t.first][t.second] + 1;     //将上一个点距离起点的距离加一给当前点
                q[++tt] = {x, y};   //把符合条件的x,y点入队, 插入到队尾
            }  //依次看t周围可经过的四个点,如果满足条件,就上下左右的顺序依次进队,一层一层的找
        }
    }
    return d[n-1][m-1];//返回终点到起点的距离
}

int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> g[i][j];
    cout << bfs() << endl;
    return 0;
}

1091. 二进制矩阵中的最短路径 - 力扣（LeetCode）

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短畅通路径的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的畅通路径是一条从左上角单元格（即，(0, 0)）到右下角单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度是该路径途经的单元格总数。

1 2	输入：grid = [[0,1],[1,0]] 输出：2

1 2	输入：grid = [[0,0,0],[1,1,0],[1,1,0]] 输出：4

1 2	输入：grid = [[1,0,0],[1,1,0],[1,1,0]] 输出：-1

AC代码

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || n == 0) return -1;
        // 定义8个方向
        int dx[8] = {-1,0,1,0,-1,-1,1,1};
        int dy[8] = {0,1,0,-1,1,-1,-1,1};
        queue<pair<int,int >>q;
        q.push({0,0});
        int path = 1; // 答案初始值是1
        
        while (q.size()) { 
            int size = q.size();
            while (size--) {
                auto t = q.front();
                q.pop();
                //扫到终点直接返回即可
                if (t.first == n - 1 && t.second == n - 1) return path; 
                for (int i = 0; i < 8; i++) {
                    int a = t.first + dx[i], b = t.second + dy[i];
                    if (a >= 0 && a < n && b >= 0 && b < n && grid[a][b] == 0 )
                    {
                        q.push({a, b});
                        grid[a][b] = 1; // 访问过的标记为1


                    }
                }
                
            }
            path++;

        }

        return -1;



    }
};