[Leetcode] Walls and Gates(BFS)

286. Walls and Gates

You are given an m x ngrid roomsinitialized 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 = 2147483647to represent INFas 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]]

Constraints:

m == rooms.length

n == rooms[i].length

1 <= m, n <= 250

rooms[i][j] is -1, 0, or 2``31`` - 1.

How to understand?

this 2d grid has gates, walls, and empty cells. Fill the empty cells with the shortest path to the nearest gate. If it can't have the path to the nearest gate, then leave it as INF. Search all the path from the empty cell vs Search from the gate to the empty cell.

How to approach?

BFS, queue

function wallsAndGates(rooms: number[][]): void {
    const INF = 2 ** 31 - 1;
    const m = rooms.length;
    if (m === 0) return;

    const n = rooms[0].length;
    const queue: [number, number][] = [];

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (rooms[i][j] === 0) {
                queue.push([i, j]);
            }
        }
    }

    const directions = [
        [-1, 0], // up
        [1, 0],  // down
        [0, -1], // left
        [0, 1],  // right
    ];

    while (queue.length > 0) {
        const [r, c] = queue.shift()!;

        for (const [dr, dc] of directions) {
            const nr = r + dr;
            const nc = c + dc;

            if (
                nr < 0 || nr >= m ||
                nc < 0 || nc >= n ||
                rooms[nr][nc] !== INF
            ) {
                continue;
            }

            rooms[nr][nc] = rooms[r][c] + 1;
            queue.push([nr, nc]);
        }
    }
}

1. if input array is empty then return nothing.
2. set m and n as row and column length of input array.
3. create a queue which has the row and column pair in the array.
4. create double for loop to find the gate(0) in the input array and add the gate's row and column index into queue.
5. set 4 directions vector
6. create while loop to check all the items in queue
7. check the first element in the queue and parse it as row and column.
8. in for loop, check the nearest 4 cells from the first item. when it is out of the bounds or it's not INF then ignore it.
9. when it's empty then add +1 for the cell and add the row and column pair in the queue. because it needs to be checked later.
10. the rooms input array is filled with the shortest path to the nearest gate.

summary

Using queue, and BFS to check the shortest path to the nearest gate. Think of this way, when the gate is already fixed position in the grid, then spread the cell one by one to mark it as "this is the shortest path from this gate".