[Google Question][LeetCode] Walls and Gates

Problem: You are given an m x n grid rooms initialized with these three possible values.

• -1 A wall or an obstacle.
• 0 A gate.
• INF Infinity means an empty room. We use the value 2^31 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Input: rooms = [[-1]]
Output: [[-1]]

Input: rooms = [[2147483647]]
Output: [[2147483647]]

Input: rooms = [[0]]
Output: [[0]]

Approach: Given that we need to find the minimum distance, it's obvious that we need to apply BFS here. We can start BFS from each gate and store the distance in the empty cells. That's all!

Implementation in C#:

    public void WallsAndGates(int[][] rooms) 

    {

        List<int[]> gatePoints = new List<int[]>();

        int rows = rooms.Length;

        int cols = rooms[0].Length;

        for (int i = 0; i < rows; ++i)

        {

            for (int j = 0; j < cols; ++j)

            {

                if (rooms[i][j] == 0)

                {

                    gatePoints.Add(new int[] {i, j});

                }

            }

        }

        Queue<int[]> queue = new Queue<int[]>();

        foreach(int[] point in gatePoints)

        {

            queue.Enqueue(point);

        }

        int distance = 0;

        while(queue.Count > 0)

        {

            int size = queue.Count;

            for (int i = 0; i < size; ++i)

            {

                int[] point = queue.Dequeue();

                

                this.AddValidNeighbors(point, rooms, queue, distance);

            }

            ++distance;

        }

    }

    

    private void AddValidNeighbors(int[] point, int[][] rooms, Queue<int[]> queue, int distance)

    {

        // down neighbor

        if (this.IsValidPoint(point[0] + 1, point[1], rooms))

        {

            rooms[point[0] + 1][point[1]] = distance + 1;

            queue.Enqueue(new int[] {point[0] + 1, point[1]});

        }

        // Up neighbor

        if (this.IsValidPoint(point[0] - 1, point[1], rooms))

        {

            rooms[point[0] - 1][point[1]] = distance + 1;

            queue.Enqueue(new int[] {point[0] - 1, point[1]});

        }

        // Left neighbor

        if (this.IsValidPoint(point[0], point[1] - 1, rooms))

        {

            rooms[point[0]][point[1] - 1] = distance + 1;

            queue.Enqueue(new int[] { point[0], point[1] - 1 });

        }

        // Right neighbor

        if (this.IsValidPoint(point[0], point[1] + 1, rooms))

        {

            rooms[point[0]][point[1] + 1] = distance + 1;

            queue.Enqueue(new int[] {point[0], point[1] + 1});

        }

    }

    

    private bool IsValidPoint(int x, int y, int[][] rooms)

    {

        if (x < 0 || x >= rooms.Length || y < 0 || y >= rooms[0].Length || rooms[x][y] != int.MaxValue)

        {

            return false;

        }

        return true;

    }

Complexity: O(m*n) where m is number of rows and n is the number of columns of the input matrix.