Java, better solution with Union-Find, 100% (time)
\nDifferent from the best reputation solution, we don\u2019t split a square into 4 parts.\n\nAs you can see, each square has 4 vertexes, so the N x N grid can b
- - - \nDifferent from the best reputation solution, we don\u2019t split a square into 4 parts.\n\nAs you can see, each square has 4 vertexes, so the N x N grid can be seen as a (N + 1) x (N + 1) vertex network.\n\nIn the beginning, the out-ring 4N vertexes form a connected component, inner (N-1)^2 vertexes form (N-1)^2 connected components independently, we have only one region.\n\nFor each square:\n\n* If input is \u2018 \u2019, we do nothing;\n* If input is \u2018/\u2019, we connect lower left vertex with upper right vertex;\n* If input is \u2018\\\\\u2019, we connect upper left vertex with lower right vertex.\n\n**As you might see, before we connect two vertexes together, if they belong to the same connected component, then the number of regions will plus one after they are connected together.**\n\nThat\u2019s the key point.\n\nAn easy-to-understand program:\n\n```\nclass Solution {\n    public int regionsBySlashes(String[] grid) {\n        int n = grid[0].length();\n        int cnt = 1;\n        UnionFind uf = new UnionFind(n + 1);\n        for (int row = 0; row < n; row++) {\n            for (int col = 0; col < n; col++) {\n                char op = grid[row].charAt(col);\n                if (op == \'/\') {\n                    if (uf.isConnected(row, col + 1, row + 1, col))\n                        cnt += 1;\n                    uf.union(row, col + 1, row + 1, col);\n                } else if (op == \'\\\\\') {\n                    if (uf.isConnected(row, col, row + 1, col + 1))\n                        cnt += 1;\n                    uf.union(row, col, row + 1, col + 1);\n                }\n            }\n        }\n        return cnt;\n    }\n}\n\nclass UnionFind {\n    private int width;\n    private int size;\n    private int[] parent;\n    private int[] weight;\n\n    public UnionFind(int n) {\n        width = n;\n        size = n * n;\n        parent = new int[size];\n        weight = new int[size];\n\n        for (int i = 0; i < size; i++)\n            parent[i] = i;\n        int gap = size - n;\n        for (int i = 0; i < n; i++) {\n            parent[i] = 0;\n            parent[i + gap] = 0;\n        }\n        gap = n - 1;\n        for (int i = 0; i < size; i += n) {\n            parent[i] = 0;\n            parent[i + gap] = 0;\n        }\n\n        weight[0] = n * 4 - 4;\n        for (int i = 1; i < size; i++)\n            weight[i] = 1;\n    }\n\n    private int index(int row, int col) {\n        return row * width + col;\n    }\n\n    private int find(int x) {\n        while (x != parent[x]) {\n            parent[x] = parent[parent[x]];\n            x = parent[x];\n        }\n        return x;\n    }\n\n    public void union(int rowP, int colP, int rowQ, int colQ) {\n        int rootP = find(index(rowP, colP));\n        int rootQ = find(index(rowQ, colQ));\n        if (rootP == rootQ)\n            return;\n        if (weight[rootP] < weight[rootQ]) {\n            parent[rootP] = rootQ;\n            weight[rootQ] += weight[rootP];\n        } else {\n            parent[rootQ] = rootP;\n            weight[rootP] += weight[rootQ];\n        }\n    }\n\n    public boolean isConnected(int rowP, int colP, int rowQ, int colQ) {\n        return find(index(rowP, colP)) == find(index(rowQ, colQ));\n    }\n\n}\n```\n\n---\n\nOptimized version (merge isConnected with union), 100% (time):\n\n```\nclass Solution {\n    public int regionsBySlashes(String[] grid) {\n        int cnt = 1;\n        UnionFind uf = new UnionFind(grid.length + 1);\n        for (int row = 0; row < grid.length; row++)\n            for (int col = 0; col < grid.length; col++)\n                cnt += uf.union(row, col, grid[row].charAt(col));\n        return cnt;\n    }\n}\n\nclass UnionFind {\n    private int width;\n    private int[] parent;\n    private int[] weight;\n\n    public UnionFind(int n) {\n        width = n;\n        int size = n * n;\n        parent = new int[size];\n        weight = new int[size];\n        for (int i = 0; i < size; i++)\n            parent[i] = i;\n        int gap = size - n;\n        for (int i = 0; i < n; i++) {\n            parent[i] = 0;\n            parent[i + gap] = 0;\n        }\n        gap = n - 1;\n        for (int i = 0; i < size; i += n) {\n            parent[i] = 0;\n            parent[i + gap] = 0;\n        }\n        weight[0] = n * 4 - 4;\n        for (int i = 1; i < size; i++)\n            weight[i] = 1;\n    }\n\n    private int find(int x) {\n        while (x != parent[x]) {\n            parent[x] = parent[parent[x]];\n            x = parent[x];\n        }\n        return x;\n    }\n\n    public int union(int row, int col, char op) {\n        if (op == \' \')\n            return 0;\n        int rootP, rootQ;\n        if (op == \'/\') {\n            rootP = find(row * width + col + 1);\n            rootQ = find((row + 1) * width + col);\n        } else {\n            rootP = find(row * width + col);\n            rootQ = find((row + 1) * width + col + 1);\n        }\n        if (rootP == rootQ)\n            return 1;\n        if (weight[rootP] < weight[rootQ]) {\n            parent[rootP] = rootQ;\n            weight[rootQ] += weight[rootP];\n        } else {\n            parent[rootQ] = rootP;\n            weight[rootP] += weight[rootQ];\n        }\n        return 0;\n    }\n}\n```\n
[]