Walls and Gates

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 296 ms)

Metric	Value
Runtime	296 ms
Memory	34.5 MB
Date	2019-12-16

Solution

public class Point 
{
    public int x;
    public int y;
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    public void WallsAndGates(int[][] rooms)
{
    int m = rooms.Length;
    int n = m == 0 ? 0 : rooms[0].Length;
    List<int[]> dirs = new List<int[]>() {
        new int[] { -1, 0 },
        new int[] { 1, 0 },
        new int[] { 0, 1 },
        new int[] { 0, -1 }
    };
    Queue<Point> queue = new Queue<Point>();
    // add all gates to the queue
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (rooms[i][j] == 0)
            {
                queue.Enqueue(new Point(i, j));
            }
        }
    }
    // update distance from gates
    while (queue.Count != 0)
    {
        var curPos = queue.Dequeue();
        foreach (var dir in dirs)
        {
            int X = curPos.x + dir[0];
            int Y = curPos.y + dir[1];
            if (X < 0 || Y < 0 || X >= m || Y >= n || rooms[X][Y] != Int32.MaxValue) continue;
            rooms[X][Y] = rooms[curPos.x][curPos.y] + 1;
            queue.Enqueue(new Point(X, Y));
        }
    }   
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed