[并查集]并查集应用之水位上升的泳池中游泳

题目

水位上升的泳池中游泳

在一个 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) 是连通的

提示:

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

分析

本次还是一道连通性判断的问题，题目核心是要判断何时从第一个分量到最后一个分量能够连通，变化是随着时间推移，分量的连通性判断会随着变化，所以需要做的事情是在每次连通性发生变化时动态增加连通关系直到第一个分量和最后一个分量相连。

题目拆解

1、矩阵中每个点是并查集中的一个分量

2、随时间推移，当相邻两个水槽都被水灌满的时候，两个水槽连通。

3、直到最后一个分量和第一个分量连通时，返回当前时间。

解题步骤（粗暴）

1、构建并查集，矩阵中有多少元素就构建多少个分量

2、写一个while循环，循环退出条件是第一个分量和最后一个分量连通，每次循环时间增加1

3、每次循环中，遍历矩阵中所有分量的连通性，如果连通，则进行合并。

代码编写 (粗暴)

并查集构建

class SwimInWaterUnionFind {

    // 存储连分量
    protected int[] id;
    // 当前并查集不同的连通分量总数
    protected int count;
    // 分量权重数组,数组里的值代表当前分量下的分量数量
    private int[] weightArr;

    public SwimInWaterUnionFind(int n) {
        // 初始化时,没个分量互不连通
        this.count = n;
        // 初始化一个容纳全量分量的数组
        this.id = new int[n];
        for (int i = 0; i < n; i++) {
            // 没个分量初始值指向自身
            id[i] = i;
        }
        weightArr = new int[n];
        // 初始化权重数组,初始化是每个分量下的权重都为1
        for (int i = 0; i < weightArr.length; i++) {
            weightArr[i] = 1;
        }
    }

    void union(int p, int q) {
        // 找到p的标识
        int pId = find(p);
        // 找到q的标识
        int qId = find(q);

        // 如果两个标识相等,代表已经合并
        if (pId == qId) return;

        // 将权重小的树,合并到权重大的树下
        if (weightArr[pId] < weightArr[qId]) {
            id[pId] = qId;
            weightArr[qId] += weightArr[pId];
        } else {
            id[qId] = pId;
            weightArr[pId] += weightArr[qId];
        }

        // 每次合并操作,会降低一个不同分量组
        count--;
    }

    int find(int p) {
        if (p == id[p]) return p;
        // 递归直接找到根节点,将分量直接指向根节点,完成彻底的路径压缩.
        id[p] = find(id[p]);
        return id[p];
    }

    boolean isConnect(int p, int q) {
        return find(p) == find(q);
    }
}

算法逻辑

public static int swimInWater(int[][] grid) {

        rowCount = grid.length;
        colCount = grid[0].length;

        int size = colCount * rowCount;
        SwimInWaterUnionFind uf = new SwimInWaterUnionFind(size);

        int time = 0;
        int[][] dir = new int[][]{{-1, 0}, {0, -1}};

        Map<Integer, Boolean> index2LinkMap = new HashMap<>();
        index2LinkMap.put(0, true);
        for (int i = 1; i < size; i++) {
            index2LinkMap.put(i, false);
        }
        while (!uf.isConnect(0, size - 1)) {
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    // 如果该点已经与第一个点连通,直接循环下一个
                    if (index2LinkMap.get(getRealIndex(i, j))) continue;
                    // 每个点判断和左侧以及上方区域是否连通
                    for (int[] ints : dir) {
                        int x = i + ints[0];
                        int y = j + ints[1];
                        // 如果越界,跳出循环
                        if (!inArea(x, y)) continue;
                        if (uf.isConnect(getRealIndex(i, j), getRealIndex(x, y))) continue;
                        // 如果当前时间下两个池子都满了,代表连通
                        if (grid[i][j] <= time && grid[x][y] <= time) {
                            uf.union(getRealIndex(i, j), getRealIndex(x, y));
                            if (uf.isConnect(0, getRealIndex(i, j))) {
                                index2LinkMap.put(getRealIndex(i, j), true);
                            }
                        }

                    }
                }
            }
            time++;
        }
        return time - 1;
    }

经过执行后，这个算法时间复杂度很高，因为每次都是全量遍历所有的分量，浪费了很多性能。

注意到题目中的提示 grid[i][j] 是 [0, …, N*N – 1] 的排列 说明矩阵中的分量是连续递增的，也就是说，时间每增加1，连通关系发生变化的分量只有一个，只要针对这一个分量进行连通性的判断即可，不需要判断全部分量。

代码编写（优化）

优化点分析

1、遍历水槽，按照递增顺序维护水槽高度与分量次序的关系。

2、每次时间增加1，将本次新被灌满的水槽与周围（上下左右）四个水槽进行连通性的判断

3、每次执行后判断最后一个分量与第一个分量是否连通，如果连通，跳出循环。

算法逻辑

public static int swimInWater(int[][] grid) {
        N = grid.length;

        int len = N * N;
        // 下标：方格的高度，值：对应在方格中的坐标
        int[] index = new int[len];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                index[grid[i][j]] = getRealIndex(i, j);
            }
        }

        SwimInWaterUnionFind uf = new SwimInWaterUnionFind(len);
        for (int i = 0; i < len; i++) {
            int x = index[i] / N;
            int y = index[i] % N;

            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];
                if (inArea(newX, newY) && grid[newX][newY] <= i) {
                    uf.union(index[i], getRealIndex(newX, newY));
                }

                if (uf.isConnect(0, len - 1)) {
                    return i;
                }
            }
        }
        return -1;
    }