---
tags: leetcode
---

# [1254. Number of Closed Islands](https://leetcode.com/problems/number-of-closed-islands/description/)
---
# My Solution
## Solution 1: DFS
### The Key Idea for Solving This Coding Question
### C++ Code

#define WHITE (0) // not visited
#define GRAY  (1) // visiting this node and its descendants.
#define BLACK (2) // have visited this node and all its descendants.

#define LAND (0)
#define WATER (1)

class Solution {
public:
    int closedIsland(vector<vector<int>> &grid) {
        rows = grid.size();
        cols = grid[0].size();

        vector<vector<int>> state(rows, vector<int>(cols, WHITE));

        for (int r = 0; r < rows; ++r) {
            if(state[r][0] == WHITE && grid[r][0] == LAND) {
                dfs(grid, state, r, 0);
            }
            if(state[r][cols - 1] == WHITE && grid[r][cols - 1] == LAND) {
                dfs(grid, state, r, cols - 1);
            }
        }
        for (int c = 0; c < cols; ++c) {
            if(state[0][c] == WHITE && grid[0][c] == LAND) {
                dfs(grid, state, 0, c);
            }
            if(state[rows - 1][c] == WHITE && grid[rows - 1][c] == LAND) {
                dfs(grid, state, rows - 1, c);
            }
        }

        int numOfIslands = 0;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (state[r][c] == WHITE && grid[r][c] == LAND) {
                    dfs(grid, state, r, c);
                    ++numOfIslands;
                }
            }
        }

        return numOfIslands;
    }

private:
    int rows;
    int cols;

    void dfs(vector<vector<int>> &grid, vector<vector<int>> &state, int r, int c) {
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

        state[r][c] = GRAY;
        for (auto &dir : dirs) {
            int nextR = r + dir[0], nextC = c + dir[1];
            if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC ||
                state[nextR][nextC] != WHITE || grid[nextR][nextC]) {
                continue;
            }
            dfs(grid, state, nextR, nextC);
        }
        state[r][c] = BLACK;
    }
};

### Time Complexity
$O(mn)$
$m$ is the number of rows in `grid`
$n$ is the number of columns in `grid`
### Space Complexity
$O(mn)$
$m$ is the number of rows in `grid`
$n$ is the number of columns in `grid`
## Solution 2: BFS
### The Key Idea for Solving This Coding Question
### C++ Code

#define WHITE (0)
#define GRAY  (1)
#define BLACK (2)

#define LAND (0)
#define WATER (1)

struct cell {
    int r;
    int c;
    cell(int r, int c) : r(r), c(c) {}
};

class Solution {
public:
    int closedIsland(vector<vector<int>> &grid) {
        rows = grid.size();
        cols = grid[0].size();
        vector<vector<int>> state(rows, vector<int>(cols, WHITE));

        for (int r = 0; r < rows; ++r) {
            if (state[r][0] == WHITE && grid[r][0] == LAND) {
                bfs(grid, state, r, 0);
            }
            if (state[r][cols - 1] == WHITE && grid[r][cols - 1] == LAND) {
                bfs(grid, state, r, cols - 1);
            }
        }
        for (int c = 0; c < cols; ++c) {
            if (state[0][c] == WHITE && grid[0][c] == LAND) {
                bfs(grid, state, 0, c);
            }
            if (state[rows - 1][c] == WHITE && grid[rows - 1][c] == LAND) {
                bfs(grid, state, rows - 1, c);
            }
        }

        int numOfIslands = 0;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (state[r][c] == WHITE && grid[r][c] == LAND) {
                    bfs(grid, state, r, c);
                    ++numOfIslands;
                }
            }
        }

        return numOfIslands;
    }

private:
    int rows;
    int cols;

    void bfs(vector<vector<int>> &grid, vector<vector<int>> &state, int r, int c) {
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<cell> q;

        q.push(cell(r, c));
        state[r][c] = GRAY;
        while (!q.empty()) {
            cell curr = q.front();
            q.pop();

            for (auto &dir : dirs) {
                int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC ||
                    state[nextR][nextC] != WHITE || grid[nextR][nextC] != LAND) {
                    continue;
                }
                q.push(cell(nextR, nextC));
                state[nextR][nextC] = GRAY;
            }
            state[curr.r][curr.c] = GRAY;
        }
    }
};

### Time Complexity
$O(mn)$
$m$ is the number of rows in `grid`
$n$ is the number of columns in `grid`
### Space Complexity
$O(mn)$
$m$ is the number of rows in `grid`
$n$ is the number of columns in `grid`
# Miscellaneous
<!--
# Test Cases

[[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]]

[[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]

[[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]]

-->