C# Accepted DFS Easy Understand Solution with inline explanation


  • 0
    I
    public void WallsAndGates(int[,] rooms)
            {
                for(int i=0;i<rooms.GetLength(0);i++)
                    for (int j = 0; j < rooms.GetLength(1); j++)
                    {
                        if (rooms[i, j] == 0)    // Find a gate 
                            Dfs(rooms, i, j);    //  Start from a gate, travel to all rooms via Dfs
                    }
            }
    
            struct Point   
            {
                public int X { private set; get; }
    
                public int Y { private set; get; }
    
                public Point(int i, int j) : this()
                {
                    X = i;
                    Y = j;
                }
            }
    
            private void Dfs(int[,] rooms, int i, int j)
            {
                Stack<Point> s = new Stack<Point>();  // Using stack to do iterative Dfs 
                s.Push(new Point(i,j));  // Push gate point to stack 
                while (s.Count != 0)   // while stack is not empty
                {
                    Point p = s.Peek();   // get stack top point as current stand point 
                    if (p.X > 0 && rooms[p.X, p.Y] + 1 < rooms[p.X - 1, p.Y])  
                     // check point above current stand point, if its value less than current stand point value + 1
                     // means shorter distance for point(p.X - 1, p.Y) is found, reset its value and push into stack
                    {
                        s.Push(new Point(p.X - 1, p.Y));
                        rooms[p.X - 1, p.Y] = rooms[p.X, p.Y] + 1;
                    }
                    else if (p.Y < rooms.GetLength(1) - 1 && rooms[p.X, p.Y] + 1 < rooms[p.X, p.Y + 1])
                    {
                        //shorter distance for point(p.X, p.Y+1) is found, reset its value and push into stack
                        s.Push(new Point(p.X, p.Y + 1));
                        rooms[p.X, p.Y + 1] = rooms[p.X, p.Y] + 1;
                    }
                    else if (p.X < rooms.GetLength(0) - 1 && rooms[p.X, p.Y] + 1 < rooms[p.X + 1, p.Y])
                    {
                        //shorter distance for point(p.X + 1, p.Y) is found, reset its value and push into stack
                        s.Push(new Point(p.X + 1, p.Y));
                        rooms[p.X + 1, p.Y] = rooms[p.X, p.Y] + 1;
                    }
                    else if (p.Y > 0 && rooms[p.X, p.Y] + 1 < rooms[p.X, p.Y - 1])
                    {
                        //shorter distance for point(p.X, p.Y-1) is found, reset its value and push into stack
                        s.Push(new Point(p.X, p.Y - 1));
                        rooms[p.X, p.Y - 1] = rooms[p.X, p.Y] + 1;
                    }
                    else
                        s.Pop();   // nowhere to go, pop current stand point out of stack 
                }
            }

Log in to reply
 

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