leetcode/javascript/0286-walls-and-gates.js at main · neetcode-gh/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * https://leetcode.com/problems/walls-and-gates/
 * Time O(ROWS * COLS) | Space O(ROWS * COLS)
 * @param {number[][]} rooms
 * @return {void} Do not return anything, modify rooms in-place instead.
 */
var wallsAndGates = function (rooms) {
    const [rows, cols] = [rooms.length, rooms[0].length];

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            const isGate = rooms[row][col] === 0;
            if (!isGate) continue;

            dfs(rooms, row, col);
        }
    }
};

const dfs = (rooms, row, col) => {
    const [rows, cols] = [rooms.length, rooms[0].length];

    for (const [_row, _col] of getNeighbors(row, rows, col, cols)) {
        const isPreviousDistanceGreater =
            rooms[_row][_col] <= rooms[row][col] + 1;
        if (isPreviousDistanceGreater) continue;

        rooms[_row][_col] = rooms[row][col] + 1;

        dfs(rooms, _row, _col);
    }
};

var getNeighbors = (row, rows, col, cols) =>
    [
        [0, 1],
        [0, -1],
        [1, 0],
        [-1, 0],
    ]
        .map(([_row, _col]) => [row + _row, col + _col])
        .filter(
            ([_row, _col]) =>
                0 <= _row && 0 <= _col && _row < rows && _col < cols,
        );

/**
 * https://leetcode.com/problems/walls-and-gates/
 * Time O(ROWS * COLS) | Space O(ROWS * COLS)
 * @param {number[][]} rooms
 * @return {void} Do not return anything, modify rooms in-place instead.
 */
var wallsAndGates = function (rooms) {
    const queue = searchGrid(rooms);

    bfs(rooms, queue);
};

const searchGrid = (rooms, queue = new Queue([])) => {
    const [rows, cols] = [rooms.length, rooms[0].length];

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            const isGate = rooms[row][col] === 0;
            if (!isGate) continue;

            queue.enqueue([row, col]);
        }
    }

    return queue;
};

const bfs = (rooms, queue) => {
    while (!queue.isEmpty()) {
        for (let i = queue.size() - 1; 0 <= i; i--) {
            checkNeighbors(rooms, queue);
        }
    }
};

const checkNeighbors = (rooms, queue) => {
    const [rows, cols] = [rooms.length, rooms[0].length];
    const [row, col] = queue.dequeue();

    for (const [_row, _col] of getNeighbors(row, rows, col, cols)) {
        const isINF = rooms[_row][_col] === 2147483647; /* (2 ** 31) - 1 */
        if (!isINF) continue;

        rooms[_row][_col] = rooms[row][col] + 1;
        queue.enqueue([_row, _col]);
    }
};

var getNeighbors = (row, rows, col, cols) =>
    [
        [0, 1],
        [0, -1],
        [1, 0],
        [-1, 0],
    ]
        .map(([_row, _col]) => [row + _row, col + _col])
        .filter(
            ([_row, _col]) =>
                0 <= _row && 0 <= _col && _row < rows && _col < cols,
        );