【每日算法Day 7】由斜杠划分区域：熟悉并查集

题目链接

LeetCode 959. 由斜杠划分区域 (opens new window)

题目描述

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。（请注意，反斜杠字符是转义的，因此 \ 用 \\ 表示。）。返回区域的数目。

提示：

1. 1 <= grid.length == grid[0].length <= 30

2. grid[i][j] 是 '/'、'\'、或 ' '。

示例

该题的示例需要结合图来理解，目前我还没有找一些好用的图床来配合博客使用，具体的示例请移步原题链接。

输入1：
[
  " /",
  "/ "
]
输出1：2

输入2：
[
  "/\\",
  "\\/"
]
输出2：5

解题思路

对于每个grid[i][j]对应的block，斜线、反斜线一共将其划分为4个小三角，从上方的开始按顺时针依次编号为0,1,2,3，则斜线将其分为[0,3]和[1,2]，反斜线将其分为[0,1]和[2,3]，空格将其分为[0,1,2,3]。则创建一个大小为4*length*length的并查集，每个block内根据grid[i][j]进行合并，同时block之间相邻的小三角也要进行合并操作。全部合并完之后，返回并查集中的连通块（树）的总数。

public class No959_RegionsCutBySlashes {
    public int regionsBySlashes(String[] grid) {
        int length=grid.length;
        UnionFind uf=new UnionFind(4*length*length);
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                int blockId=i*length+j;
                //合并块内的4个小三角
                switch (grid[i].charAt(j)) {
                    case '/':
                        uf.union(blockId*4,blockId*4+3);
                        uf.union(blockId*4+1,blockId*4+2);
                        break;
                    case '\\':
                        uf.union(blockId*4,blockId*4+1);
                        uf.union(blockId*4+2,blockId*4+3);
                        break;
                    case ' ':
                        uf.union(blockId*4,blockId*4+1);
                        uf.union(blockId*4+1,blockId*4+2);
                        uf.union(blockId*4+2,blockId*4+3);
                        break;
                }
                //合并块间
                if (i>0)//和上方合并
                    uf.union(blockId*4,(blockId-length)*4+2);
                if (i<length-1)//和下方合并
                    uf.union(blockId*4+2,(blockId+length)*4);
                if (j>0)//和左方合并
                    uf.union(blockId*4+3,(blockId-1)*4+1);
                if (j<length-1)//和右方合并
                    uf.union(blockId*4+1,(blockId+1)*4+3);
            }
        }
        return uf.getUniqueTreeCount();
    }

    private class UnionFind{
        int[] parent;

        public UnionFind(int length) {
            parent=new int[length];
            for (int i = 0; i < length; i++) {
                parent[i]=i;
            }
        }

        //由于这题需要给出并查集中数的数目，所以直接使用完全压缩
        public int find(int x) {
            if (parent[x] != x) {
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x), rootY = find(y);
            parent[rootX]=rootY;
        }

        public int getUniqueTreeCount() {
            int count=0;
            for (int i = 0; i < parent.length; i++) {
                if (i==find(i))
                    count++;
            }
            return count;
        }
    }
}

总结

这一题我先想的思路和官方的题解一致，只是具体的变量命名方式、计算表达式不同。然而，在具体实现的时候由于流程和表达式繁杂想要得出正确的结果还是得非常细心，例如在上面的switch语句中后面两种情况忘记写break;导致最终合并完的结果异常。（看了官方的写法，其实可以用两个!=的if判断来涵盖三种情况）