Islands

• Number of Islands
• Number of Closed Islands

Number of Islands

Leetcode: 200

Given an m x n 2d grid map of'1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

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

public int NumIslands(char[][] grid)
{
    int m = grid.Length;
    int n = grid[0].Length;
    bool[,] visited = new bool[m, n];
    int count = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == '1' && !visited[i, j])
            {
                //if the element is 1 mark all neighboring 1s as visited
                //so it is the land which is surrounded by water (0s)
                MarkDfs(grid, visited, i, j);
                count++;
            }
        }
    }
    return count;
}

public void MarkDfs(char[][] grid, bool[,] visited, int i, int j)
{
    if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length
         || visited[i, j] || grid[i][j] == '0')
        return;


    visited[i, j] = true;

    MarkDfs(grid, visited, i - 1, j);
    MarkDfs(grid, visited, i + 1, j);
    MarkDfs(grid, visited, i, j - 1);
    MarkDfs(grid, visited, i, j + 1);
}

Number of Closed Islands

Leetcode: 1254

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:

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).

public int ClosedIsland(int[][] grid)
{
    int m = grid.Length;
    int n = grid[0].Length;
    bool[,] visited = new bool[m, n];
    int count = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 0 && !visited[i, j])
            {
                bool isCorner = false;
                ClosedDfs(grid, visited, i, j, ref isCorner);
                if (isCorner) continue;
                count++;
            }
        }
    }
    return count;
}

public void ClosedDfs(int[][] grid, bool[,] visited, int i, int j, ref bool isCorner)
{
    if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length || visited[i, j] || grid[i][j] == 1)
        return;

    //update isCorner every time.
    isCorner = isCorner || (i == 0 || i == grid.Length - 1 || j == grid[0].Length - 1 || j == 0);
    visited[i, j] = true;

    ClosedDfs(grid, visited, i - 1, j, ref isCorner);
    ClosedDfs(grid, visited, i + 1, j, ref isCorner);
    ClosedDfs(grid, visited, i, j - 1, ref isCorner);
    ClosedDfs(grid, visited, i, j + 1, ref isCorner);
}