C# solution: DFS, check all cells


  • 0
    B
    public class Solution 
    {
        public int NumIslands(char[,] grid) 
        {
            var row = grid.GetLength(0);
            var col = grid.GetLength(1);
    
            int count = 0;
    
            var isVisited = new bool[row, col];
    
            for(int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (grid[i, j] == '1' && !isVisited[i, j])
                    {
                        DFS(grid, isVisited, i, j);
                        count++;
                    }
                }
            }
    
            return count;
        }
    
        private void DFS(char[,] grid, bool[,] isVisited, int i, int j)
        {
            var row = grid.GetLength(0);
            var col = grid.GetLength(1);
    
            if (i < 0 || i >= row || j < 0 || j >= col) return;
    
            if (isVisited[i, j]) return;
    
            isVisited[i, j] = true;
    
            if (grid[i, j] == '0') return;
    
            // else grid[i, j] == '1'
            var directions = new Tuple<int,int>[]{ Tuple.Create(0,1), Tuple.Create(0,-1), Tuple.Create(1,0), Tuple.Create(-1, 0) };
    
            foreach(var direction in directions)
            {
                var nextX = i + direction.Item1;
                var nextY = j + direction.Item2;
    
                DFS(grid, isVisited, nextX, nextY);
            }
        }
    }
    

Log in to reply
 

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