↓快轉到主要內容
  1. Leetcode/

[LeetCode] 959. Regions Cut by Slashes

·
LeetCode DFS Union Find
目錄

題目連結：959. Regions Cut by Slashes

題目敘述
#

An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.

Given the grid grid represented as a string array, return the number of regions.

Note that backslash characters are escaped, so a '\' is represented as '\\'.

解題思路
#

解法一
#

我們可以將 grid 的每一個格子看成是一個 3 * 3 的九宮格。

  • 如果格子是 '/'，我們可以將其轉換為：
0 0 1
0 1 0
1 0 0
  • 如果格子是 '\\'，則可以轉換為：
1 0 0
0 1 0
0 0 1

只要可以將斜線與反斜線轉換成等效的地圖後之後就簡單了，我們可以使用 DFS，把尚未走過的格子走過一遍，一邊紀錄孤立的區域數量即可。

解法二
#

另外一個方法是使用 Union-Find (disjoint set)。

我們將每個 grid 格子看作有四個端點。也就是說，一個 n * n 的 grid，總共有 n+1 * n+1 個點。

在定義好圖的表示法後，我們可以使用 Union-Find 來將相連的點連起來。

那麼怎麼知道這些點連出孤立一個的區域呢？當我們在 union 兩個點時，如果這兩個點的 parent 相同，則表示將這兩個點相連後形成了一個封閉區域。

因此，我們的流程如下：

  1. 首先我們初始化 Union-Find 資料結構，首先將 grid 最外圍的點都 union 起來。

  2. 開始遍歷 grid 中的每個格子：

    • 如果格子是 '/' 的話，代表格子右上與左上的端點相連。
    • 如果格子是 '\\' 的話，則代表左上與右下的端點相連。
    • 在每次 union 的時候，如果兩點的 parent 相同，則說明形成了一個孤立的區域，因此 region_count + 1。

在所有相連的點都 union 後，region_count 就是我們的答案了。

程式碼
#

C++
#

解法一
#

class Solution {
public:
    int vec[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

    void dfs(int y, int x, vector<vector<int>>& g, vector<vector<bool>>& visit, int n) {
        visit[y][x] = true;

        for (int i = 0; i < 4; i++) {
            int ny = y + vec[i][0];
            int nx = x + vec[i][1];
            
            if (ny < 0 || ny >= n * 3 || nx < 0 || nx >= n * 3)
                continue;
            if (g[ny][nx] == 1 || visit[ny][nx])
                continue;
            
            dfs(ny, nx, g, visit, n);
        }
    }

    int regionsBySlashes(vector<string>& grid) {
        int res = 0;
        int n = grid.size();
        vector<vector<int>> g(n * 3, vector<int>(n * 3));
        vector<vector<bool>> visit(n * 3, vector<bool>(n * 3, false));

        for (int i = 0 ; i < n; i++) {
            for (int j = 0 ; j < n; j++) {
                int y = i * 3;
                int x = j * 3;

                switch(grid[i][j]) {
                case '/':
                    g[y][x+2] = g[y+1][x+1] = g[y+2][x] = 1;
                    break;
                case '\\':
                    g[y][x] = g[y+1][x+1] = g[y+2][x+2] = 1;
                    break;
                }
            }
        }

        for (int i = 0; i < n * 3; i++) {
            for (int j = 0; j < n * 3; j++) {
                if (g[i][j] == 0 && !visit[i][j]) {
                    dfs(i, j, g, visit, n);
                    res += 1;
                }
            }
        }

        return res;
    }
};

解法二
#

class Solution {
public:
    int region_count;
    vector<int> parent;
    vector<int> rank;

    int Find(int a) {
        if (parent[a] != a)
            return parent[a] = Find(parent[a]);
        return a;
    }

    void Union(int a, int b) {
        int root_a = Find(a);
        int root_b = Find(b);

        if (root_a != root_b) {
            if (rank[root_a] > rank[root_b]) {
                parent[root_b] = root_a;
            } else if (rank[root_a] < rank[root_b]) {
                parent[root_a] = root_b;
            } else {
                parent[root_b] = root_a;
                rank[root_a]++;
            }
        } else {
            region_count++;
        }
    }

    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        int m = n + 1; // number of point in grid
        parent.resize(m * m);
        rank.resize(m * m);

        for (int i = 0; i < parent.size(); i++) {
            parent[i] = i;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || i == n || j == 0 || j == n)
                    Union(0, i * m + j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '/') {
                    int top_right = i * m + (j + 1);
                    int bottom_left = (i + 1) * m + j;
                    Union(top_right, bottom_left);
                } else if (grid[i][j] == '\\') {
                    int top_left = i * m + j;
                    int bottom_right = (i + 1) * m + (j + 1);
                    Union(top_left, bottom_right);
                }
            }
        }

        return region_count;
    }
};