Leetcode 1254. Number of Closed Islands

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1

Solution

In the DFS function, it is important to visit all eligible locations.

class Solution {
public:
    int rsize, csize;
    bool isBorder(int r, int c) {
        if (r == rsize-1  || r == 0 || c == csize -1 || c == 0 ) {
            return true;
        }
        return false;
    }
    
    int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int r, int c, bool& touchedBorder) {
        if (r>=rsize || r<0 || c>=csize || c <0 || visited[r][c] || grid[r][c] == 1) {
            return 0;
        }        
        if (isBorder(r,c) && grid[r][c] == 0){
            touchedBorder = true;
        }
        visited[r][c]=true;  
        vector<vector<int>> dir {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for (int i=0; i<4; i++) {
            dfs(grid, visited, r + dir[i][0], c + dir[i][1], touchedBorder);
        }
        return 1;
    }
    
    int closedIsland(vector<vector<int>>& grid) {
        rsize = grid.size();
        csize = grid[0].size();
        int sum = 0;
        vector<vector<bool>> visited(rsize, vector<bool>(csize, false));
 
        for (int i=0; i<rsize; i++) {
            for (int j=0; j<csize; j++) {
                bool touchedBorder = false;
                int local = dfs(grid, visited, i, j, touchedBorder);
                if (!touchedBorder) {
                    sum += local;
                }
            }
        }
        return sum;        
    }
};

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

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