Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 6

Description

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

Example 3:

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

Constraints:

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  const int MOVES[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
  int closedIsland(vector<vector<int>>& grid) {
    queue<pair<int, int>> q;
    int rows = grid.size();
    int cols = grid.front().size();
    vector<vector<bool>> visit(rows, vector<bool>(cols));

    int answer = 0;
    for(int r = 0; r < rows; ++r) {
      for(int c = 0; c < cols; ++c) {
        if(grid[r][c] || visit[r][c]) {
          visit[r][c] = true;
          continue;
        }
        q.push({r, c});
        visit[r][c] = true;
        bool border = false;
        while(q.size()) {
          auto [row, col] = q.front();
          q.pop();
          if(!row || !col || row == rows - 1 || col == cols - 1) {
            border = true;
          }
          for(int m = 0; m < 4; ++m) {
            int newRow = row + MOVES[m][0];
            int newCol = col + MOVES[m][1];
            if(newRow < 0 || newCol < 0 || newRow >= rows || newCol >= cols) continue;
            if(grid[newRow][newCol] || visit[newRow][newCol]) continue;
            visit[newRow][newCol] = true;
            q.push({newRow, newCol});
          }
        }
        if(!border) {
          // cout << r << ' ' << c << endl;
          answer += 1;
        }
      }
    }

    return answer;
  }
};

// Accepted
// 47/47 cases passed (16 ms)
// Your runtime beats 43.87 % of cpp submissions
// Your memory usage beats 23.2 % of cpp submissions (10.3 MB)