算法leetcode

【搜索难题】力扣778-水位上升的泳池中游泳

字数统计: 1.5k字   |   阅读时长: 6分
, , ,

摘要: 一个搜索题，可以用优先级队列 BFS 或者值域二分解决

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

本文我们看一个搜索题。有两个解法，一个是值域二分+DFS、另一个是优先级队列 BFS，都是搜索问题中非常常见的算法。

$1 题目

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

提示:

1
2
3
4
5
n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n^2
grid[i][j] 中每个值 均无重复

示例 1:
输入: grid = [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

示例 2:
输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
输出: 16
解释: 最终的路线用加粗进行了标记。
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

$2 题解

算法1：优先级队列 BFS

完全套用 BFS 找两点间路径的模板，但是队列用优先级队列，队列里存的是下一个可选的点，而出队的时候将高度最低的先出队。

维护一个已经出队元素高度的最大值，当终点弹出队列时，这个维护的最大值就是答案。

例如下图中，从起点BFS到终点的过程中，所有出队的元素用粉色的线标出，这写粉色标记的节点，高度最高的就是答案。

代码(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
struct Node
{
    int x, y, h;
    Node(int i, int j, int height):x(i),y(j),h(height){}
};

struct Cmp
{
    bool operator() (const Node& node1, const Node& node2)
    {
        return node1.h > node2.h; // 小顶堆
    }
};

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int N = grid.size(); // 调用方保证 N >= 2
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        priority_queue<Node, vector<Node>, Cmp> pq;
        vector<vector<bool> > visited(N, vector<bool>(N, false));
        // 记录到达 grid[N - 1][N - 1] 经过路线的最大高度, 和最小高度
        int maxh = grid[0][0];
        visited[0][0] = true;
        pq.push(Node(0, 0, grid[0][0]));
        while(!pq.empty())
        {
            Node cur = pq.top();
            pq.pop();
            maxh = max(maxh, cur.h);
            if(cur.x == N - 1 && cur.y == N - 1)
                return maxh;
            for(int d = 0; d < 4; ++d)
            {
                int x = cur.x + dx[d];
                int y = cur.y + dy[d];
                if(!_check(x, y, N) || visited[x][y])
                    continue;
                pq.push(Node(x, y, grid[x][y]));
                visited[x][y] = true;
            }
        }
        return -1;
    }

private:
    bool _check(int x, int y, int N)
    {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
};

算法2：值域二分 + DFS

二分一般有两种二分，一种是对元素下标二分，left, right 是元素下标，mid = (left + right) / 2，根据条件判断的结果判断答案在哪一半。

另一种是对值域的二分，然后也是根据条件判断的结果，退出答案应该在哪一半。例如猜物品价格，已知了物品的上限和下限，每次都猜中间价格，如果没有猜对，必须有一个反馈，告诉我当前猜的是高了还是低了。

本体数据范围给了：

1
grid[i][j] 位于区间 [0, ..., N*N - 1] 内。

那么答案一定在 0 ~ N*N-1 之间，left = 0, right = N * N - 1。

每次取 mid = (left + right) / 2，然后根据条件判断函数 check(mid) 的结果，做出答案是猜大了还是猜小了的结论。

这里的 check 函数就是 dfs，从左上点出发，只要是相邻点，且高度 <= mid 就往下 dfs，如果 dfs 到了终点，说明当前猜的值 mid 一定 >= 答案，如果没有 dfs 到终点，说明猜的值 mid 一定 < 答案。不断猜下去直至 left == right,left 就是答案。

代码(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
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int N = grid.size();
        int left = 0, right = N * N - 1;
        vector<vector<bool> > visited(N, vector<bool>(N, false));
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(grid[0][0] > mid)
            {
                left = mid + 1;
                continue;
            }
            visited.clear();
            visited.assign(N, vector<bool>(N, false));
            visited[0][0] = true;
            if(dfs(grid, visited, 0, 0, mid, N))
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }

private:
    bool dfs(const vector<vector<int> >& grid, vector<vector<bool> >& visited, int i, int j, int max_h, int N)
    {
        if(i == N - 1 && j == N - 1)
            return true;
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        for(int d = 0; d < 4; ++d)
        {
            int x = i + dx[d];
            int y = j + dy[d];
            if(!_check(x, y, N) || visited[x][y] || grid[x][y] > max_h)
                continue;
            visited[x][y] = true;
            if(dfs(grid, visited, x, y, max_h, N))
                return true;
        }
        return false;
    }

    bool _check(int x, int y, int N)
    {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
};
Share