bfs解决最短步数问题

前置知识

1. 队列：一种先进先出，队头出队，队尾入队的数据结构。
2. 广度优先搜索（bfs）：每次从队列中取出一个节点，将该节点相邻的未搜索的节点加入队列中，循环上述过程，这就是广度优先搜索。
3. 图：由顶点和边相互连接形成的数据结构。
4. 邻接矩阵：用来表示顶点之间的连通状态的二维数组。

要点

• 存：按照题目提示，定义好每一步需要在队列中储存的信息，包括但不限于：坐标、是否走过某点、消耗物及其消耗情况等。
• 起：确定地图中起点的坐标。
• 终：确定地图中终点的坐标。
• 转：状态转移，即走过每一个点后每个点相关信息应该怎样变化。
• 重：考虑去重方法。

例题

LeetCode 934. 最短的桥

描述

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

思路

• 存：坐标x、坐标y、当前行走步数l。
• 起：其中一个岛屿的所有坐标，l = 0。
• 终：另外一个岛屿的任意一个坐标，返回其步数。
• 转：每次搜寻下一个点的坐标、l++。
• 重：起点和走过的点标记为2。

代码

class Solution {
private:
    struct node
    {
        int x, y;
        int l;
    };
    int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
    queue<node> que;
    void dfs_join(vector<vector<int>>& grid, int x, int y)
    {
        grid[x][y] = 2;
        que.push((node){x, y, 0});
        for(int i = 0; i < 4; i++)
        {
            int tx = x + dir[i][0], ty = y + dir[i][1];
            if(tx < 0 || tx >= grid.size() || ty < 0 || ty >= grid[0].size() || !grid[tx][ty] || grid[tx][ty] == 2) continue;
            dfs_join(grid, tx, ty);
        }
    }
    void find_start(vector<vector<int>>& grid)
    {
        for(int i = 0; i < grid.size(); i++)
        {
            for(int j = 0; j < grid[0].size(); j++)
            {
                if(grid[i][j])
                {
                    dfs_join(grid, i, j);
                    return;
                }
            }
        }
    }
public:
    int shortestBridge(vector<vector<int>>& grid) {
        int i, j;
        find_start(grid);
        while(!que.empty())
        {
            int x = que.front().x, y = que.front().y;
            for(int i = 0; i < 4; i++)
            {
                int tx = x + dir[i][0], ty = y + dir[i][1];
                if(tx < 0 || tx >= grid.size() || ty < 0 || ty >= grid[0].size() || grid[tx][ty] == 2) continue;
                if(grid[tx][ty]) return que.front().l;
                grid[tx][ty] = 2;
                que.push((node){tx, ty, que.front().l + 1});
            }
            que.pop();
        }
        return 0;
    }
};

相关题目

LeetCode 864. 获取所有钥匙的最短路径

LeetCode 417. 太平洋大西洋水流问题

LeetCode 529. 扫雷游戏