Walls and Gates: BFS with Pruning

If you look at this problem, it can become a N^3 one with N=250, which starts to get a little slow. It will be a BFS for each gate, but the pruning will happen primarily due to this condition here. Basically we'll only proceed with the BFS while the cells being reached have a greater (or equal to) number of steps. It is easy to understand: suppose that you're performing the BFS given a certain gate and you run into a cell which has a number-of-steps-to-a-gate equal to 5 but with the current BFS that value is 6. You don't want to update OR continue in that path since the value that was there was already better than the one you're "suggesting". Code is down below, cheers, and Happy ThxGiving!!!

Walls and Gates - LeetCode

286. Walls and Gates

Medium

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 231 - 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 1:

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]]

Example 2:

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

Example 3:

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

Example 4:

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

 

Constraints:

• m == rooms.length
• n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] is -1, 0, or 231 - 1.

Accepted

184,691

Submissions

318,389

public class Solution {
    public class WallsAndGatesQueueItem
    {
        public int row = 0;
        public int col = 0;
        public int numberSteps = 0;
        public int key = 0;

        public WallsAndGatesQueueItem(int row, int col, int numberSteps)
        {
            this.row = row;
            this.col = col;
            this.numberSteps = numberSteps;
            this.key = row * 255 + col;
        }
    }
    public void WallsAndGates(int[][] rooms)
    {
        List gateRow = new List();
        List gateCol = new List();

        for (int r = 0; r < rooms.Length; r++)
        {
            for (int c = 0; c < rooms[r].Length; c++)
            {
                if (rooms[r][c] == 0)
                {
                    gateRow.Add(r);
                    gateCol.Add(c);
                }
            }
        }

        for (int i = 0; i < gateRow.Count; i++)
        {
            int gr = gateRow[i];
            int gc = gateCol[i];

            Queue queue = new Queue();
            Hashtable visited = new Hashtable();
            WallsAndGatesQueueItem queueItem = new WallsAndGatesQueueItem(gr, gc, 0);
            visited.Add(queueItem.key, true);
            queue.Enqueue(queueItem);

            while (queue.Count > 0)
            {
                WallsAndGatesQueueItem currentItem = queue.Dequeue();

                int[] rowDelta = { 1, -1, 0, 0 };
                int[] colDelta = { 0, 0, 1, -1 };

                for (int j = 0; j < rowDelta.Length; j++)
                {
                    int newRow = currentItem.row + rowDelta[j];
                    int newCol = currentItem.col + colDelta[j];

                    if (newRow >= 0 &&
                        newRow < rooms.Length &&
                        newCol >= 0 &&
                        newCol < rooms[newRow].Length &&
                        currentItem.numberSteps + 1 <= rooms[newRow][newCol])
                    {
                        WallsAndGatesQueueItem newItem = new WallsAndGatesQueueItem(newRow, newCol, currentItem.numberSteps + 1);
                        if (!visited.ContainsKey(newItem.key))
                        {
                            rooms[newRow][newCol] = newItem.numberSteps;
                            visited.Add(newItem.key, true);
                            queue.Enqueue(newItem);
                        }
                    }
                }
            }
        }
    }
}