Leetcode discuss: 1254. Number of Closed Islands

March 30, 2022

Here is the link. 

C# | DFS | Closed island | first row or last row or first column or last column

March 29, 2022
Problem statement:
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.

Closed islands | Find all nodes in one island | Determine if any node is on the border of matrix
Start from any node in given matrix with value 0, and run DFS search and visit all nodes in the same island, mark visited to set value as 1, and also check if the node is in the first row or last row or first column or last column. If there is one found, then the island is not a closed island.

The following statement is easy to follow, if island is closed then return true, do nothing. Otherwise check if the current row is the first or last row or current col is the first or last column.

 foundNotClosed = foundNotClosed || row == 0 || row == (rows - 1) || col == 0 || col == (columns - 1);

My first submission had an issue: index-out-of-range, runDFS function if statement col >= columns, but = is missing.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1254_number_of_closed_islands
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new Program();
            var grid = new int[5][];
            grid[0] = new int[]{1,1,1,1,1,1,1,0};
             grid[1] = new int[]{1,0,0,0,0,1,1,0};
             grid[2] = new int[]{1,0,1,0,1,1,1,0};
             grid[3] = new int[]{1,0,0,0,0,1,0,1};
             grid[4] = new int[]{1,1,1,1,1,1,1,0};

             var count = test.ClosedIsland(grid);            
        }

        public int ClosedIsland(int[][] grid)
        {
            if (grid == null || grid.Length == 0 || grid[0].Length == 0)
                return 0;

            var rows = grid.Length;
            var columns = grid[0].Length;

            var count = 0;
            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < columns; col++)
                {
                    if (grid[row][col] == 1)
                        continue;

                    var foundNotClosed = false;

                    runDFS(grid, row, col, ref foundNotClosed);
                    if (!foundNotClosed)
                    {
                        count++;
                    }
                }
            }

            return count; 
        }

        private void runDFS(int[][] grid, int row, int col, ref bool foundNotClosed)
        {
            var rows = grid.Length;
            var columns = grid[0].Length;
            if (row < 0 || row >= rows || col < 0 || col >= columns || grid[row][col] == 1)
            {
                return; 
            }

            foundNotClosed = foundNotClosed || row == 0 || row == (rows - 1) || col == 0 || col == (columns - 1);

            grid[row][col] = 1;

            runDFS(grid, row, col + 1, ref foundNotClosed);
            runDFS(grid, row, col - 1, ref foundNotClosed);
            runDFS(grid, row - 1, col, ref foundNotClosed);
            runDFS(grid, row + 1, col, ref foundNotClosed);
        }
    }
}