[LeetCode][Medium] 1254. Number of Closed Islands

Leetcode 網址: https://leetcode.com/problems/number-of-closed-islands/

題目說明:

題目大意是要從一個二維地圖中，找出所有"完全被海包圍的陸地"，

如果陸地在地圖邊界，則不算 "完全被海包圍的陸地"。

解題說明:

這題很直覺，我們就是直接藉由 DFS 去訪問那些陸地，

如果訪問陸地途中碰到邊界，則代表該陸地沒有完全被海包圍，

如果訪問完連續的陸地也沒碰到邊界，則代表該陸地有完全被海包圍。

程式碼

class Solution {
public:
    bool traverseIsland(vector<vector<int>>& grid, int x, int y)
    {
        if (y < 0 || x < 0 || y >= grid.size() || x >= grid[0].size()) return false;
        if (grid[y][x]) return true;
        grid[y][x] = 1;
        bool isClosedIsland = traverseIsland(grid, x - 1, y);
        isClosedIsland = isClosedIsland & traverseIsland(grid, x + 1, y);
        isClosedIsland = isClosedIsland & traverseIsland(grid, x, y - 1);
        return isClosedIsland & traverseIsland(grid, x, y + 1);
    }
    
    int closedIsland(vector<vector<int>>& grid) {
        int count = 0, width = grid[0].size(), height = grid.size();
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                count += (grid[i][j] == 0 && traverseIsland(grid, j, i)) ? 1 : 0;
            }
        }
        return count;
    }
};

結果

Runtime: 20 ms, faster than 94.31% of C++ online submissions for Number of Closed Islands.

Memory Usage: 9.7 MB, less than 79.72% of C++ online submissions for Number of Closed Islands.