Skip to content

Latest commit

 

History

History
132 lines (98 loc) · 4.31 KB

README.md

File metadata and controls

132 lines (98 loc) · 4.31 KB

778. 水位上升的泳池中游泳

English Version

题目描述

在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。

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

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？

 

示例 1:

输入: [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。

等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

示例2:

输入: [[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
解释:
 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，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

 

提示:

  1. 2 <= N <= 50.
  2. grid[i][j] 是 [0, ..., N*N - 1] 的排列。

解法

Python3



Java



class Solution {
    // x、y方向向量
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    /**
     * https://blog.csdn.net/fuxuemingzhu/article/details/82926674
     * <p>
     * 参考这篇文章的第二种解题方法做的
     * <p>
     * 通过优先级队列找寻局部最优解  最终的得到的结果就是全局最优解
     *
     * @param grid
     * @return
     */
    // 以grid左上角为原点，横向为X轴，纵向为Y轴
    public int swimInWater(int[][] grid) {
        // 定义一个优先级队列  按照h从小到大排列
        Queue<Pair<Integer, Pair<Integer, Integer>>> queue = new PriorityQueue<>(Comparator.comparing(Pair::getKey));
        queue.add(new Pair<>(grid[0][0], new Pair<>(0, 0)));
        // 已经遍历过的点
        Set<Pair<Integer, Integer>> visitSet = new HashSet<>();
        visitSet.add(new Pair<>(0, 0));

        int res = 0;
        int length = grid.length;

        while (!queue.isEmpty()) {
            Pair<Integer, Pair<Integer, Integer>> top = queue.poll();
            Integer x = top.getValue().getKey();
            Integer y = top.getValue().getValue();
            res = Math.max(res, top.getKey());
            // 2 <= N <= 50 这个范围内可以直接使用==进行Integer的比较
            if (x == top.getValue().getValue() && y == length - 1) {
                break;
            }

            for (int i = 0; i < 4; i++) {
                int newY = y + dy[i];
                int newX = x + dx[i];
                if (newX < 0 || newY < 0 || newX >= length || newY >= length || visitSet.contains(new Pair<>(newX, newY))) {
                    // 直接忽略
                    continue;
                }
                queue.add(new Pair<>(grid[newX][newY], new Pair<>(newX, newY)));
                visitSet.add(new Pair<>(newX, newY));
            }
        }
        return res;
    }
}


...