devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】BFS类型题目总结_c++与门

作者：IT小白 | 2024-05-02 00:10:10

赞

踩

c++与门

文章目录

一. FloodFill 系列

1、墙与门

题目连接

题目描述：
在这里插入图片描述
注意：

  • m == rooms.length
  • n == rooms[i].length
  • 1 <= m, n <= 250
  • rooms[i][j] 是 -1、0 或 231 - 1

解题思路：
核心在于用队列把只存门和空房间的位置，把墙排除在外。刚好门的值为0，这样拿出队列里的每一个元素，搜索它的上下左右位置有没有空房间，有的话更新空房间的最近门距离就是该元素的值+1，之后把空房间的位置也入队列，继续拿出队列的下一个元素去更新它周围空房间的值。

  • 遍历数组，把所有门的下标入队列。
  • 依次拿出队列的元素，检查该元素的上下左右位置是否有空房间，有的话空房间的值改为：刚从队列拿出元素的值 + 1，就是该位置空房间的最近的门距离，之后把空房间的下标也入队列。重复前面的动作直到队列为空。

完整代码：

class Solution 
{
private:
    int around[4][2] = 
        {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
        };

public:
    void wallsAndGates(vector<vector<int>>& rooms) 
    {
        queue<pair<int, int>> q;
        int m = rooms.size();
        int n = rooms[0].size();
        // 1、先把所有的门都入队列
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(rooms[i][j] == 0)
                {
                    q.push(make_pair(i, j));
                }
            }
        }
        // 2、依次拿出队列里的坐标，看看该位置的上下左右是否有空房间
        // 如果有空房间，那么空房间的最近门距离就是该位置的值+1，完成后原来空房间的坐标入队列
        while(!q.empty())
        {
            pair<int, int> pr = q.front();
            q.pop();
            int row = pr.first;
            int col = pr.second;
            for(int i=0; i<4; ++i)
            {
                int newRow = row + around[i][0];
                int newCol = col + around[i][1];
                if(newRow<0 || newRow>=m || newCol<0 || newCol>=n || rooms[newRow][newCol] != INT_MAX)
                {
                    continue;
                }
                rooms[newRow][newCol] = rooms[row][col] + 1;
                q.push(make_pair(newRow, newCol));
            }
        }
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

性能分析：

  • 时间复杂度：O(m*n)。
  • 空间复杂度：O(m*n)。最坏情况全部都是门，全部入队列

2、图像渲染

图像渲染

题目描述：
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例：

输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出:
[[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意：

  • image 和 image[0] 的长度在范围 [1, 50] 内。
  • 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
  • image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

解题思路：
给定一个位置，记该位置颜色为curColor，把这个位置附近的所有这个curColor颜色的区域块染成newColor。典型的单路径BFS，注意搜索前要先把当前位置的颜色染成newColor。

完整代码：

class Solution 
{
private:
    // 控制上下左右四个方向
    int distance[4][4] = 
    {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0}
    };

    int m, n, pColor; //把经常用到的变量设为类的成员变量，这样类的成员函数都能直接拿到

    void bfs(vector<vector<int>>& image, pair<int, int> pr, int color)
    {
        // 一个数据入队列后，记得要把它的颜色改了
        queue<pair<int, int>> q;
        q.push(pr);
        image[pr.first][pr.second] = color;
        while(!q.empty())
        {
            auto [row, col] = q.front();
            q.pop();
            for(int k = 0; k < 4; ++k)
            {
                int newRow = row + distance[k][0];
                int newCol = col + distance[k][1];
                if(newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && image[newRow][newCol] == pColor)
                {
                    image[newRow][newCol] = color;
                    q.push({newRow, newCol});
                }
            }
        }
    }

public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        // 0、预处理
        pColor = image[sr][sc];
        if(pColor == color) return image;
        // 1、数据初始化
        m = image.size();
        n = image[0].size();
        // 2、bfs
        bfs(image, make_pair(sr, sc), color);
        // 3、返回值
        return image;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

性能分析：

  • 时间复杂度：O(n*m)。最坏情况这个矩阵颜色都是curColor。
  • 空间复杂度：O(n*m)。队列的开销。

3、01 矩阵

题目连接

题目描述：
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

在这里插入图片描述
在这里插入图片描述
注意：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1
  • mat 中至少有一个 0

解题思路：
多路径源的搜索问题，考虑创建一个超级0来作为搜索时的标识。一开始把原矩阵中所有值为0的下标入队列，然后BFS搜索。

完整代码：

class Solution 
{
    int constExr[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) 
    {
        // 1、创建
        // 最终返回的结果矩阵ret
        // 用来标志多路径源集合的矩阵super，一开始把mat中值为0的下标对应到super中标志为1
        // bfs时用到的存储下标键值对的队列，一开始把所有值为0的下标入队列
        int row = mat.size();
        int col = mat[0].size();
        vector<vector<int>> ret(row, vector<int>(col));
        vector<vector<int>> super(row, vector<int>(col));
        queue<pair<int, int>> q;
        for(int i = 0; i < row; ++i)
        {
            for(int j = 0; j < col; ++j)
            {
                if(mat[i][j] == 0)
                {
                    q.push(make_pair(i, j));
                    super[i][j] = 1;
                }
            }
        }
        // 2、进行多路径的广度优先搜索
        while(!q.empty())
        {
            pair<int, int> front = q.front();
            int i = front.first;
            int j = front.second;
            q.pop();
            for(int d = 0; d < 4; ++d)
            {
                int ni = i+constExr[d][0];
                int nj = j+constExr[d][1];
                if(ni>=0 && ni<row && nj>=0 && nj<col && !super[ni][nj])
                {
                    q.push(make_pair(ni, nj));
                    ret[ni][nj] = ret[i][j] + 1;
                    super[ni][nj] = 1;
                }
            }
        }
        // 返回结果矩阵ret
        return ret;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

性能分析：

  • 时间复杂度：O(n*m)。最坏情况遍历整个数组。
  • 空间复杂度：O(n*m)。队列的开销。

4、岛屿数量

题目连接

题目描述：
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

在这里插入图片描述
注意：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 ‘0’ 或 ‘1’

解题思路：
创建一个队列，遍历数组如果遇到岛屿的话ret加一，并把岛屿的值改为’0’和它的下标入队列，如果队列不为空就取出队列的元素，搜索该位置的上下左右是否还有其他岛屿，有的话也同样把岛屿的值改为’0’和它的下标入队列，直到最后队列为空就算排除一座岛屿。

完整代码：

class Solution 
{
private:
    int around[4][2]=
    {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };

public:
    int numIslands(vector<vector<char>>& grid) 
    {
        int ret = 0;
        queue<pair<int, int>> q;
        int m = grid.size();
        int n = grid[0].size();
        // 1、遍历数组，遇到岛屿ret就加一
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                // 2、遇到岛屿ret就加一，把该岛屿下标入队列，并把其值置为'0'
                if(grid[i][j] == '1')
                {
                    q.push(make_pair(i, j));
                    ++ret;
                    // 搜索入栈岛屿的上下左右位置是否还有其他岛屿，有的话也入队列，把值置为'0'
                    // 直到最后队列为空，就算排除了一座岛屿
                    while(!q.empty())
                    {
                        int row = q.front().first;
                        int col = q.front().second;
                        grid[row][col] = '0';
                        q.pop();
                        for(int k=0; k<4 ;++k)
                        {
                            int newRow = row+around[k][0];
                            int newCol = col+around[k][1];
                            if(newRow<0 || newRow>=m || newCol<0 || newCol>=n || grid[newRow][newCol] != '1')
                            {
                                continue;
                            }
                            grid[newRow][newCol] = '0';
                            q.push(make_pair(newRow, newCol));
                        }
                    }
                }
            }
        }
        return ret;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54

性能分析：

  • 时间复杂度：O(m*n)。
  • 空间复杂度：O(min(m, n))。最坏情况全部是岛屿，因为一次可以排除该位置的上下左右，所以最多队列一次性存储元素的长度为min(m, n)。

5、岛屿的最大面积

题目链接

题目描述
给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例一
在这里插入图片描述

示例二
输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 为 0 或 1

解题思路
每次 bfs 就是去找一块相联的岛屿，在这个过程中统计岛屿的面积

完整代码

class Solution 
{
private:
    int distance[4][4] = 
    {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
    };

    int m, n;

    int bfs(vector<vector<int>>& grid, pair<int, int> pr)
    {
        // 第一个岛屿先入队列
        queue<pair<int, int>> q;
        q.push(pr);
        grid[pr.first][pr.second] = 0;
        int count = 1;
        // 合并周围岛屿
        while(!q.empty())
        {
            auto [row, col] = q.front();
            q.pop();
            for(int k = 0; k < 4; ++k)
            {
                int newRow = row + distance[k][0];
                int newCol = col + distance[k][1];
                if(newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1)
                {
                    ++count;
                    q.push({newRow, newCol});
                    grid[newRow][newCol] = 0;
                }
            }
        }
        // 返回值
        return count;
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid1)
    {
        vector<vector<int>> grid(grid1);
        // 1、数据初始化
        m = grid.size(), n = grid[0].size();
        // 2、数据处理
        int ret = 0;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(grid[i][j] == 1)
                    ret = max(ret, bfs(grid, make_pair(i, j)));
        // 3、返回值
        return ret;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

6、钥匙和房间

题目连接

题目描述：
在这里插入图片描述
解题思路：
最初，除 0 号房间外的其余所有房间都被锁住，我们从0号房间开始搜索，遍历每个房间中其他房间的钥匙，搜索过程中统计可以进入的房间数量并标记每个房间是否已经进入。

完整代码：

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) 
    {
        // 1、定义了三个对象
        // q：用来进行BFS的存储房间下标的队列
        // count：统计能进入房间的数量
        // vis：标记每个房间是否有被进入过
        queue<int> q;
        int count = 0;
        vector<bool> vis(rooms.size(), false);
        // 2、第0号房间先入队列进行BFS
        q.push(0);
        ++count;
        vis[0] = true;
        while(!q.empty())
        {
            int front = q.front();
            q.pop();
            // 遍历当前房间中其他房间的钥匙
            for(auto e : rooms[front])
            {
                if(!vis[e])
                {
                    q.push(e);
                    ++count;
                    vis[e] = true;
                }
            }
        }
        // 3、最终返回记录的count是否等于总的房间数
        return count == rooms.size();
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

性能分析：

  • 时间复杂度：O(n+m)。n为房间总数，m为所有房间中钥匙的总数。
  • 空间复杂度：O(n)。队列和vis的开销。

7、机器人移动范围

题目连接

题目描述：
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

输入描述：
一行三个正整数由空格分开，分别代表行数m，列数n，和坐标数位之和的阈值k，0 < m <= 100, 0 < n <= 100, 0 < k <= 20。

输出描述：
一个正整数，代表该机器人能够到达的格子数量。

示例：

输入：
3 3 6
输出：
9

解题思路：
从(0, 0)开始向上下左右四个方向搜索，如果坐标合法、坐标数位之和不大于k，并且没有被访问过就把这个坐标入队列。

完整代码：

#include <queue>
#include <utility>
#include <vector>
#include <iostream>
using namespace std;

// 判断当前格子能否进入
bool IsEnter(int m, int n, int k)
{
  int sum = 0;
  while(m)
  {
    sum += m%10;
    m /= 10;
  }
  while(n)
  {
    sum += n%10;
    n /= 10;
  }
  return sum <= k;
}

int PathRange(vector<vector<bool>>& matrix, int k)
{
  // 1、定义相关对象
  // matrix：标记格子的访问情况
  // count：统计机器人能够达到多少个格子
  // q：进行BFS的存储坐标键值对的队列
  int count = 0;
  queue<pair<int, int>> q;
  // 2、从坐标0,0的格子开始搜索
  if(IsEnter(0, 0, k))
  {
    matrix[0][0] = true;
    ++count;
    q.push(make_pair(0, 0));
  }
  while(!q.empty())
  {
    pair<int, int> front = q.front();
    int m = front.first;
    int n = front.second;
    q.pop();
	// 上下左右四个方向搜索
    if(m-1>=0 && !matrix[m-1][n] && IsEnter(m-1, n, k))
    {
      matrix[m-1][n] = true;
      ++count;
      q.push(make_pair(m-1, n));
    }
    if(m+1<(int)matrix.size() && !matrix[m+1][n] && IsEnter(m+1, n, k))
    {
      matrix[m+1][n] = true;
      ++count;
      q.push(make_pair(m+1, n));
    }
    if(n-1>=0 && !matrix[m][n-1] && IsEnter(m, n-1, k))
    {
      matrix[m][n-1] = true;
      ++count;
      q.push(make_pair(m, n-1));
    }
    if(n+1<(int)matrix[0].size() && !matrix[m][n+1] && IsEnter(m, n+1, k))
    {
      matrix[m][n+1] = true;
      ++count;
      q.push(make_pair(m, n+1));
    }
  }
  // 3、count就是最终到达的格子数
  return count;
}

int main()
{
  int row = 0;
  int col = 0;
  int k = 0;
  cin>>row>>col>>k;
  vector<vector<bool>> matrix(row, vector<bool>(col, false));
  cout<<PathRange(matrix, k)<<endl;
  return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84

性能分析：

  • 时间复杂度：O(m*n)。最多每一个格子都能到达。
  • 空间复杂度：O(m*n)。队列的开销。

8、被围绕的区域


题目链接

题目描述
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

在这里插入图片描述

示例 2：
输入：board = [[“X”]]
输出：[[“X”]]

提示

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 ‘X’ 或 ‘O’

解题思路
该题因为边界情况比较特殊，直接处理的话不好处理，正难则反，我们先把边界 ’ O ’ 的相联区域用 ’ *’ 都给替换掉，最后再遍历一遍数组：

  • 如果遇到 ’ O ’ ，把它用 ’ X’ 给替换掉
  • 如果遇到 ’ * ’ ，把它还原成 ’ O ’

完整代码

class Solution
{
private:
    vector<vector<int>> distance = 
    {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
    };

    int m, n;

    void bfs(vector<vector<char>>& board, int i, int j, char ch)
    {
        // 初始化
        queue<pair<int, int>> q;
        q.push({i, j});
        board[i][j] = ch;
        // bfs
        while(!q.empty())
        {
            auto [row, col] = q.front();
            q.pop();
            for(int d = 0; d < 4; ++d)
            {
                int newRow = row + distance[d][0];
                int newCol = col + distance[d][1];
                if(newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'O')
                {
                    q.push({newRow, newCol});
                    board[newRow][newCol] = ch;
                }
            }
        }
    }


public:
    void solve(vector<vector<char>>& board) 
    {
        // 1、数据初始化
        m = board.size(), n = board[0].size();
        queue<pair<int, int>> q;
        // 2、bfs 把边界的 'O' 用 'X' 填充
        for(int j = 0; j < n; ++j)
        {
            if(board[0][j] == 'O')     bfs(board, 0, j, '*');
            if(board[m - 1][j] == 'O') bfs(board, m - 1, j, '*');
        }
        for(int i = 0; i < m; ++i)
        {
            if(board[i][0] == 'O')     bfs(board, i, 0, '*');
            if(board[i][n - 1] == 'O') bfs(board, i, n - 1, '*');
        }
        // 3、还原
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == '*') board[i][j] = 'O';

    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

二. 最短路径问题

1、迷宫中离入口最近的出口

题目链接

题目描述
给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。

请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

示例一
在这里插入图片描述

示例二
在这里插入图片描述

提示

  • maze.length == m
  • maze[i].length == n
  • 1 <= m, n <= 100
  • maze[i][j] 要么是 ‘.’ ，要么是 ‘+’ 。
  • entrance.length == 2
  • 0 <= entrancerow < m
  • 0 <= entrancecol < n
  • entrance 一定是空格子。

解题思路
从起始位置开始 bfs，每次把上下左右四个方向能走的位置入队列，然后出的时候，把上一批能走的点位全部出出来，继续重复 bfs，如果谁先走到边界了，谁就是最短路径

完整代码

class Solution 
{
private:
    vector<vector<int>> distance = 
    {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
    };

public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
    {
        // 1、数据初始化
        int m = maze.size();
        int n = maze[0].size();
        queue<pair<int, int>> q;
        q.push({entrance[0], entrance[1]});
        vector<vector<bool>> vis(m, vector<bool>(n));
        vis[entrance[0]][entrance[1]] = true;

        // 2、bfs
        int step = 0;
        while(!q.empty())
        {
            ++step;
            for(int i = q.size(); i > 0; --i)
            {
                auto [row, col] = q.front();
                q.pop();
                for(int k = 0; k < 4; ++k)
                {
                    int newRow = row + distance[k][0];
                    int newCol = col + distance[k][1];
                    if(newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !vis[newRow][newCol] && maze[newRow][newCol] != '+')
                    {
                        if(newRow == 0 || newRow == m - 1 || newCol == 0 || newCol == n - 1) 
                        {
                            // cout << newRow << ':' << newCol;
                            return step;
                        }
                        q.push({newRow, newCol});
                        vis[newRow][newCol] = true;
                    }
                }
            }            
        }

        // 3、走不出去，返回 -1
        return -1;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/521203
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号