算法搜索

双端队列BFS

字数统计: 1.4k字   |   阅读时长: 5分
,

摘要: 基于双端队列的 BFS

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 带权图最短路径 中我们全面学习了带权图最短路径的算法，其中 BFS 是一类非常重要的算法。但是常规的 BFS 只能处理边权相同的情况，否则就需要对队列进行改进，其中一种比较特殊的情况是边的权只有 0 和 1 两种，此时可以用双端队列。

本文我们就以力扣 1368 为模板题看一下双端队列 BFS 的原理和实现。

$1 题目

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

  • 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
  • 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
  • 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
  • 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]

注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。

一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。

你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。

请你返回让网格图至少有一条有效路径的最小代价。

提示：

1
2
3
m == grid.length
n == grid[i].length
1 <= m, n <= 100

示例1
输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出：3
解释：你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为： (0, 0) —> (0, 1) —> (0, 2) —> (0, 3) 花费代价 cost = 1 使方向向下 —> (1, 3) —> (1, 2) —> (1, 1) —> (1, 0) 花费代价 cost = 1 使方向向下 —> (2, 0) —> (2, 1) —> (2, 2) —> (2, 3) 花费代价 cost = 1 使方向向下 —> (3, 3)
总花费为 cost = 3.

示例 2：
输入：grid = [[1,1,3],[3,2,2],[1,1,4]]
输出：0
解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。

示例 3：
输入：grid = [[1,2],[4,3]]
输出：1

示例 4：
输入：grid = [[2,2,2],[2,2,2]]
输出：3

示例 5：
输入：grid = [[4]]
输出：0

$2 题解

算法: 双端队列BFS

定义状态，x, y 为位置，d 为代价(改方向的次数)

1
2
3
4
5
6
struct State
{
    int x, y;
    int d;
    State(int x, int y, int d):x(x),y(y),d(d){}
};

当前状态为 cur, 对应位置 (i, j) 的时候，下一步有四个方向，这四个方向除了常规的出界判断，已访问判断，还需要判断一下与图中标识的方向是否一致，如果不一致，则代价要加 1。

1
2
3
4
if(d == grid[i][j] - 1)
    deq.push_back(State(x, y, cur.d));
else
    deq.push_front(State(x, y, cur.d + 1));

要求的是最小代价，当前转移的代价可能是 1 或 0，只要将 0 代价的从队头压入，1 代价的从队尾压入。则某个状态 state 出队时，从源点到达对应的位置 (state.x, state.y) 所需的最小代价就是 state.d，此时标记该位置已访问，visited[state.x][state.y] = true，这个标记已访问的时机与 dijkstra 是相同的。

0-1 BFS(双端队列BFS) 的思想与 Dijkstra(优先级队列BFS) 的相似性：

  • 在 Dijkstra 算法中，优先队列保证了距离的单调递增性。
  • 在 0-1 BFS中，任意时刻队列中的节点与源点的距离均为 d 或 d + 1，并且所有与源点距离为 d 的节点都出现在队首附近，所有与源点距离为 d + 1 的节点都出现在队尾附近。

因此，只要使用双端队列，对于边权为 0 和 1 的两种情况分别将对应节点添加至队首和队尾，就保证了距离的单调递增性。

代码 (C++)

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
struct State
{
    int x, y;
    int d;
    State(int x, int y, int d):x(x),y(y),d(d){}
};

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        deque<State> deq;
        deq.push_back(State(0, 0, 0));
        while(!deq.empty())
        {
            State cur = deq.back();
            deq.pop_back();
            int i = cur.x;
            int j = cur.y;
            if(i == n - 1 && j == m - 1)
                return cur.d;
            // i, j 位置已经出过队后，就不让再进队了
            visited[i][j] = true;
            for(int d = 0; d < 4; ++d)
            {
                int x = i + dx[d];
                int y = j + dy[d];
                if(x < 0 || x >= n || y < 0 || y >= m)
                    continue;
                if(visited[x][y])
                    continue;
                if(d == grid[i][j] - 1)
                    deq.push_back(State(x, y, cur.d));
                else
                    deq.push_front(State(x, y, cur.d + 1));
            }
        }
        return -1;
    }

private:
    // 右左下上
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
};
Share