bfs解决最短步数问题
前置知识
- 队列：一种先进先出，队头出队，队尾入队的数据结构。
- 广度优先搜索（bfs）：每次从队列中取出一个节点，将该节点相邻的未搜索的节点加入队列中，循环上述过程，这就是广度优先搜索。
- 图：由顶点和边相互连接形成的数据结构。
- 邻接矩阵：用来表示顶点之间的连通状态的二维数组。
要点
- 存：按照题目提示，定义好每一步需要在队列中储存的信息，包括但不限于：坐标、是否走过某点、消耗物及其消耗情况等。
- 起：确定地图中起点的坐标。
- 终：确定地图中终点的坐标。
- 转：状态转移，即走过每一个点后每个点相关信息应该怎样变化。
- 重：考虑去重方法。
例题
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;
}
};