Minimum Moves to Move a Box to Their Target Location LeetCode solution in JavaScript

1
/**
2
 * @param {character[][]} grid
3
 * @return {number}
4
 */
5
var minPushBox = function (grid) {
6
  // common info & utils
7
  const m = grid.length;
8
  const n = grid[0].length;
9
  const dirs = [
10
    [1, 0],
11
    [-1, 0],
12
    [0, 1],
13
    [0, -1],
14
  ];
15
  const add = (a, b) => [a[0] + b[0], a[1] + b[1]];
16
  const equals = (a, b) => a[0] === b[0] && a[1] === b[1];
17
  const validate = ([x, y]) => x >= 0 && y >= 0 && x < m && y < n;
18
  const getKey = ([x, y]) => x * n + y;
19

20
  // find all player, ball, target, and free cells
21
  const init = () => {
22
    let player;
23
    let ball;
24
    let target;
25
    const freeSet = new Set();
26
    for (let i = 0; i < m; i++) {
27
      for (let j = 0; j < n; j++) {
28
        if (grid[i][j] === ".") {
29
          freeSet.add(getKey([i, j]));
30
        } else if (grid[i][j] === "S") {
31
          freeSet.add(getKey([i, j]));
32
          player = [i, j];
33
        } else if (grid[i][j] === "B") {
34
          freeSet.add(getKey([i, j]));
35
          ball = [i, j];
36
        } else if (grid[i][j] === "T") {
37
          freeSet.add(getKey([i, j]));
38
          target = [i, j];
39
        }
40
      }
41
    }
42
    return { player, ball, target, freeSet };
43
  };
44
  const { player, ball, target, freeSet } = init();
45
  const targetKey = getKey(target);
46

47
  // detect whether two cells are connected
48
  const connCache = new Map(); // [x,y,x2,y2,x3,y3] => boolean
49
  const getConnKey = (a, b, ball) => {
50
    if (a[0] > b[0] || (a[0] === b[0] && a[1] > b[1])) {
51
      [a, b] = [b, a];
52
    }
53
    return [a[0], a[1], b[0], b[1], ball[0], ball[1]].join(",");
54
  };
55
  const isConnected = (a, b, ball) => {
56
    if (a[0] === b[0] && a[1] === b[1]) {
57
      return true;
58
    }
59
    const connKey = getConnKey(a, b, ball);
60
    if (connCache.has(connKey)) {
61
      return connCache.get(connKey);
62
    }
63
    const bKey = getKey(b);
64
    const ballKey = getKey(ball);
65
    const visited = new Array(m * n).fill(false);
66
    visited[getKey(a)] = true;
67
    const queue = [a];
68
    while (queue.length) {
69
      const cell = queue.shift();
70
      for (let i = 0; i < dirs.length; i++) {
71
        const next = add(cell, dirs[i]);
72
        if (validate(next)) {
73
          const nextKey = getKey(next);
74
          if (nextKey === bKey) {
75
            connCache.set(connKey, true);
76
            return true;
77
          }
78
          if (
79
            freeSet.has(nextKey) &&
80
            nextKey !== ballKey &&
81
            !visited[nextKey]
82
          ) {
83
            visited[nextKey] = true;
84
            queue.push(next);
85
          }
86
        }
87
      }
88
    }
89
    connCache.set(connKey, false);
90
    return false;
91
  };
92

93
  // solve the game
94
  const getStateKey = ([x, y], [xx, yy]) => [x, y, xx, yy].join(","); // ball, player
95
  const stateCache = new Set(); // Set<stateKey>
96
  let queue = [[ball, player]];
97
  let count = 1;
98
  while (queue.length) {
99
    const nextQueue = [];
100
    for (let i = 0; i < queue.length; i++) {
101
      const [ball, player] = queue[i];
102
      for (let j = 0; j < dirs.length; j++) {
103
        const dir = dirs[j];
104
        const reverseDir = [dir[0] ? -dir[0] : 0, dir[1] ? -dir[1] : 0];
105
        const nextBall = add(ball, dir);
106
        const nextPlayer = add(ball, reverseDir);
107
        const nextBallKey = getKey(nextBall);
108
        const nextPlayerKey = getKey(nextPlayer);
109
        if (
110
          validate(nextBall) &&
111
          validate(nextPlayer) &&
112
          freeSet.has(nextBallKey) &&
113
          freeSet.has(nextPlayerKey)
114
        ) {
115
          const nextStateKey = getStateKey(nextBall, nextPlayer);
116
          if (isConnected(player, nextPlayer, ball)) {
117
            if (!stateCache.has(nextStateKey)) {
118
              stateCache.add(nextStateKey);
119
              if (nextBallKey === targetKey) {
120
                return count;
121
              }
122
              nextQueue.push([nextBall, nextPlayer]);
123
            }
124
          }
125
        }
126
      }
127
    }
128
    queue = nextQueue;
129
    count++;
130
  }
131
  return -1;
132
};