Graph: Given a matrix, find the number of closed islands

Problem Statement:

You are given a 2D matrix. You need to find the number of closed islands.

An closed island is an island that is completely surrounded by water.

1 represents land
0 represents water

Example:

Input: mat[][] = [[1, 0, 0], 
                   [0, 1, 0], 
                   [0, 0, 1]]

Output: 1.

The cell at [1, 1] is completely surrounded by water 0.

Solution Explanation:

For each unvisited land (grid[i][j] == 1 and !visited[i][j]), perform depth first search to check if it forms a closed island.

In dfs approach, we will check if the current land is adjacent to water then recursively check its 4 neighbor(up, down, left, right) to see if they form closed island.

If the current land is not a closed island, return false.

If all the 4 neighbors form a closed island, then return true.

Time Complexity: O(mn)
Space Complexity: O(mn)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

bool dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j) 
{
    int m = grid.size();
    int n = grid[0].size();

    // Out of bounds meaning not closed
    if (i < 0 || i >= m || j < 0 || j >= n) 
    {
        return false;
    }

    if (visited[i][j]) 
    	return true;

    visited[i][j] = true;

    // Water cell is safe
    if (grid[i][j] == 0) 
    	return true;

    bool isClosed = true;
    isClosed &= dfs(grid, visited, i - 1, j);
    isClosed &= dfs(grid, visited, i + 1, j);
    isClosed &= dfs(grid, visited, i, j - 1);
    isClosed &= dfs(grid, visited, i, j + 1);

    return isClosed;
}


int solution(vector<vector<int>>& grid) 
{
    int m = grid.size();
    int n = grid[0].size();
    int count = 0;
    vector<vector<bool>> visited(m, vector<bool>(n, false));

    for (int i = 1; i < m - 1; i++) 
    {
        for (int j = 1; j < n - 1; j++) 
        {
            if (grid[i][j] == 1 && !visited[i][j]) 
            {
                bool isClosed = dfs(grid, visited, i, j);
                if (isClosed) 
                {
                    count++;
                }
            }
        }
    }
    return count;
}

int main()
{

    vector<vector<int>> matrix = 
    {
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 1}
    };

    cout << solution(matrix);
    return 0;
}

Output

1