1
/**
2
 * @param {string[]} grid
3
 * @return {number}
4
 */
5
var shortestPathAllKeys = function (grid) {
6
  const rows = grid.length,
7
    cols = grid[0].length,
8
    INF = Number.MAX_SAFE_INTEGER - 1;
9

10
  /* Find the locks and keys */
11
  let keyChars = "",
12
    start;
13
  for (let i = 0; i < rows; i++) {
14
    for (let j = 0; j < cols; j++) {
15
      let letter = grid[i][j];
16
      if (letter === "@") {
17
        start = [i, j];
18
        continue;
19
      }
20
      if (letter === "." || letter === "#") continue;
21
      if (letter >= "a") keyChars += letter;
22
    }
23
  }
24
  let lockChars = keyChars.toUpperCase();
25
  const combos = Math.pow(2, keyChars.length);
26

27
  let mask = 0x01,
28
    bitPos = {},
29
    unlocks = {};
30
  for (let i = 0; i < keyChars.length; i++) {
31
    bitPos[keyChars[i]] = mask;
32
    unlocks[lockChars[i]] = mask;
33
    mask *= 2;
34
  }
35

36
  let dp = Array(rows);
37
  for (let i = 0; i < rows; i++) {
38
    dp[i] = Array(cols);
39
    for (let j = 0; j < cols; j++) dp[i][j] = Array(combos).fill(INF);
40
  }
41
  dp[start[0]][start[1]][0] = 0;
42
  //console.log(dp);
43
  //console.log(bitPos, unlocks);
44

45
  const getNeighbors = function (r, c) {
46
    let neighbors = [];
47
    if (r > 0) neighbors.push([r - 1, c]);
48
    if (r < rows - 1) neighbors.push([r + 1, c]);
49
    if (c > 0) neighbors.push([r, c - 1]);
50
    if (c < cols - 1) neighbors.push([r, c + 1]);
51

52
    return neighbors;
53
  };
54

55
  /**** SMUSH functions to "smush" through the various terrain ****/
56
  const smushWall = (r, c, prev) => false;
57
  const smushSpace = function (r, c, prev) {
58
    let changed = false;
59
    for (let i = 0; i < prev.length; i++) {
60
      if (dp[r][c][i] > prev[i] + 1) {
61
        dp[r][c][i] = prev[i] + 1;
62
        changed = true;
63
      }
64
    }
65
    return changed;
66
  };
67
  const smushKeyFunc = function (key) {
68
    let mask = bitPos[key];
69
    const smushKey = function (r, c, prev) {
70
      let changed = false;
71
      for (let i = 0; i < prev.length; i++) {
72
        if (dp[r][c][i | mask] > prev[i] + 1) {
73
          dp[r][c][i | mask] = prev[i] + 1;
74
          changed = true;
75
        }
76
      }
77
      return changed;
78
    };
79
    return smushKey;
80
  };
81
  const smushLockFunc = function (key) {
82
    let mask = unlocks[key];
83
    const smushLock = function (r, c, prev) {
84
      let changed = false;
85
      for (let i = 0; i < prev.length; i++) {
86
        if ((i & mask) !== mask) continue;
87
        if (dp[r][c][i] > prev[i] + 1) {
88
          dp[r][c][i] = prev[i] + 1;
89
          changed = true;
90
        }
91
      }
92
      return changed;
93
    };
94
    return smushLock;
95
  };
96
  let smush = { "#": smushWall, ".": smushSpace, "@": smushSpace };
97
  for (let i = 0; i < keyChars.length; i++) {
98
    smush[keyChars[i]] = smushKeyFunc(keyChars[i]);
99
  }
100
  for (let i = 0; i < lockChars.length; i++) {
101
    smush[lockChars[i]] = smushLockFunc(lockChars[i]);
102
  }
103

104
  let minPath = INF,
105
    buf = [start];
106
  while (buf.length > 0) {
107
    let next = new Set();
108
    for (let [r, c] of buf) {
109
      let neighbors = getNeighbors(r, c);
110
      for (let [nrow, ncol] of neighbors) {
111
        if (smush[grid[nrow][ncol]](nrow, ncol, dp[r][c])) {
112
          if (dp[nrow][ncol][dp[nrow][ncol].length - 1] < INF)
113
            minPath = Math.min(
114
              minPath,
115
              dp[nrow][ncol][dp[nrow][ncol].length - 1]
116
            );
117
          else next.add([nrow, ncol]);
118
        }
119
      }
120
    }
121
    buf = [...next];
122
  }
123

124
  //console.log(bitPos);
125

126
  return minPath === INF ? -1 : minPath;
127
};