Simple & Easy to understand C# solution with explanation


  • 0
    N

    The idea is to find a land '1', discover the whole island from there, then move to the next island.
    I used DFS implementation to discover the island.

    public class Solution {
        public int NumIslands(char[,] grid) 
        {
            int islands =0;
            for (int i = 0 ; i < grid.GetLength(0) ; i++)
            {
                for (int j = 0; j <grid.GetLength(1); j++)
                {
                    if(grid[i,j] == '1')
                    {
                        islands++;
                        grid = DiscoverIsland(grid, i,j, grid.GetLength(0), grid.GetLength(1));
                    }
                }
            }
            return islands;
        }
        public char[,] DiscoverIsland(char[,] grid, int i, int j, int width, int height)
        {
            Stack<int[]> s = new Stack<int[]>();
            s.Push(new int[]{i,j});
            grid[i,j] = '2';
            while (s.Count > 0)
            {
                int[] arr = s.Peek();
                i = arr[0];
                j = arr[1];
                if(i+1 < width && grid[i+1,j] == '1')
                {
                    s.Push(new int[]{i+1,j});
                    grid[i+1,j] = '2';
                }
                else if(i-1 >= 0 && grid[i-1,j] == '1')
                {
                    s.Push(new int[]{i-1,j});
                    grid[i-1,j] = '2';
                }
                else if(j+1 < height && grid[i,j+1] == '1')
                {
                    s.Push(new int[]{i,j+1});
                    grid[i,j+1] = '2';
                }
                else if(j-1 >=0 && grid[i,j-1] == '1')
                {
                    s.Push(new int[]{i,j-1});
                    grid[i,j-1] = '2';
                }
                else
                {
                    s.Pop();
                }
            }
            return grid;
        } 
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.