[LeetCode][Medium] 959. Regions Cut By Slashes

Leetcode 網址: https://leetcode.com/problems/regions-cut-by-slashes/

題目說明:

這題跟 LeetCode 1254 非常像，給定 Grid 以及其邊線，

要找尋這些邊線切出來的 Region 總共有幾塊。

解題說明:

因為是找 Region 數量問題，所以方向很直覺就是藉由 DFS 去訪問，

不過這題比較不同的是，他給你的 Grid 是包含 "邊線" 而非 "'障礙物"，

意思也就是追要把這個 Grid 先轉換成 DFS 能 Traverse 的 Grid，

觀察題目給的幾個範例後，一開始想說把 Grid 放大成二倍，

結果遇到這個情況會過不了: ["//", "/ "]，

放大 2 倍的 Grid:

0101

1010

0100

1000

也就是說，因為只有 2 倍大的 Grid 空間不夠，進而造成連續二個 // 形成一個不存在的 region，

所以發現問題之後，嘗試改成 3 倍大確認跟預期的 Grid 無誤後 Submit 即 AC 了。

放大 3 倍的 Grid:
001001
010010
100100
001000
010000
100000

程式碼

class Solution {
public:
    int count;
    void traverseIsland(vector<vector<int>>& grid, int x, int y)
    {
        if (y < 0 || x < 0 || y >= grid.size() || x >= grid[0].size()) return;
        if (grid[y][x]) return;
        grid[y][x] = count;
        traverseIsland(grid, x - 1, y);
        traverseIsland(grid, x + 1, y);
        traverseIsland(grid, x, y - 1);
        return traverseIsland(grid, x, y + 1);
    }
    
    int regionsBySlashes(vector<string>& grid) {
        count = 0;
        vector<vector<int>> newGrid(grid.size() * 3, vector<int>(grid.size() * 3, 0));
        for (int i = 0, height = grid.size(); i < height; i++) {
            for (int j = 0, width = grid[0].length(); j < width; j++) {
                if (grid[i][j] == '/') 
                    newGrid[i * 3][j * 3 + 2] = newGrid[i * 3 + 1][j * 3 + 1] = newGrid[i * 3 + 2][j * 3] = 1;
                if (grid[i][j] == '\\') 
                    newGrid[i * 3][j * 3] = newGrid[i * 3 + 1][j * 3 + 1] = newGrid[i * 3 + 2][j * 3 + 2] = 1;
            }
        }
        for (int i = 0, height = newGrid.size(); i < height; i++) {
            for (int j = 0, width = newGrid[0].size(); j < width; j++) {
                if(!newGrid[i][j] && ++count) traverseIsland(newGrid, j, i);
            }
        }
        
        return count;
    }
};




結果

Runtime: 16 ms, faster than 65.50% of C++ online submissions for Regions Cut By Slashes.

Memory Usage: 11.8 MB, less than 44.98% of C++ online submissions for Regions Cut By Slashes.