# C# Accepted DFS Easy Understand Solution with inline explanation

• ``````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
}
}``````

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