算法搜索

优先级队列BFS

字数统计: 1.1k字   |   阅读时长: 4分
,

摘要: 基于优先级队列的 BFS

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

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

本文我们以二维接雨水问题来看一下另一种改进，也就是优先级队列 BFS，该算法的思路与用堆实现 dijkstra 带权图最短路径的算法殊途同归。

一维的接雨水问题是一个在网上已经被研究透的陈题，解法非常多，参考文章 【多解法】力扣42-接雨水。二维接雨水问题的解法思路类似于一维接雨水中的双指针算法，下面我们来看这个问题。

$1 题目

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

示例 1:

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

提示:

1
2
3
4
m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 1e4

$2 题解

算法: 优先级队列BFS

一维接雨水中有一种双指针的方法，是从两个端点向内收缩，收缩时推进高度较小的那一端。若推进后的位置高度变低，则推进后的位置可以容纳雨水。若推进后的位置高度变高或不变，则推进后的位置可以不可容纳雨水，并且需要更新端点高度为变高后的值。参考文章 【多解法】力扣42-接雨水。

二维情况的思想与一维情况的双指针的思路一样，从最外一圈往里收缩，收缩时推进高度最小的那一个点，收缩方向为4个方向中未访问过的点，可能为一个，两个或者三个。

用堆维护当前边界上的所有点，可以方便第取高度最小的点，推进的新点在标记已访问后压进堆中参选。

  • 若新点的高度降低了，则该点可以更新雨水。新点的高度维持原高度不变(在一维的双指针算法中也是这样做的)。
  • 若新点的高度升高了，则新点的高度更新为升高后的高度。

代码 (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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
struct Point
{
    int x, y, h;
    Point(int i, int j, int h):x(i),y(j),h(h){}
};

struct HeapCmp
{
    bool operator()(const Point& p1, const Point& p2) const
    {
        return p1.h > p2.h;
    }
};

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if(heightMap.empty())
            return 0;
        int n = heightMap.size(), m = heightMap[0].size();
        if(n <= 2 || m <= 2)
            return 0;
        priority_queue<Point, vector<Point>, HeapCmp> pq;
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        for(int i = 0; i < n; ++i)
        {
            pq.push(Point(i, 0, heightMap[i][0]));
            pq.push(Point(i, m - 1, heightMap[i][m - 1]));
            visited[i][0] = true;
            visited[i][m - 1] = true;
        }
        for(int j = 1; j < m - 1; ++j)
        {
            pq.push(Point(0, j, heightMap[0][j]));
            pq.push(Point(n - 1, j, heightMap[n - 1][j]));
            visited[0][j] = true;
            visited[n - 1][j] = true;
        }
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        int ans = 0;
        while(!pq.empty())
        {
            Point p = pq.top();
            pq.pop();
            for(int d = 0; d < 4; ++d)
            {
                int x = p.x + dx[d];
                int y = p.y + dy[d];
                if(x < 0 || x >= n || y < 0 || y >= m)
                    continue;
                if(visited[x][y])
                    continue;
                visited[x][y] = true;
                int h = heightMap[x][y];
                if(h < p.h)
                {
                    ans += p.h - h;
                    pq.push(Point(x, y, p.h));
                }
                else
                    pq.push(Point(x, y, h));
            }
        }
        return ans;
    }
};
Share