1
class Solution {
2
  int dirx[4] = {-1, 1, 0, 0};
3
  int diry[4] = {0, 0, 1, -1};
4

5
 public:
6
  int shortestPathAllKeys(vector<string> &grid) {
7
    int n = grid.size();
8
    int m = grid[0].size();
9
    vector<vector<int>> matrix(n, vector<int>(m));
10
    vector<int> lock(7, 0);
11
    int sx, sy;
12
    int lk = 0;
13
    for (int i = 0; i < n; i++) {
14
      for (int j = 0; j < m; j++) {
15
        if (grid[i][j] == '@') {
16
          sx = i, sy = j;
17
          matrix[i][j] = 0;
18
        } else if (grid[i][j] == '.') {
19
          matrix[i][j] = 0;
20
          // cout << grid[i][j];
21
        } else if (grid[i][j] >= 'A' && grid[i][j] <= 'F') {
22
          matrix[i][j] = -1 * ((grid[i][j] - 'A') + 1);
23
          lock[(grid[i][j] - 'A') + 1] = (1 << (grid[i][j] - 'A'));
24
        } else if (grid[i][j] == '#')
25
          matrix[i][j] = -8;
26
        else {
27
          matrix[i][j] = (1 << (grid[i][j] - 'a'));
28
          lk++;
29
        }
30
        // cout << matrix[i][j] << " ";
31
      }
32
      // cout << endl;
33
    }
34
    int fnl = (1 << lk) - 1;
35
    // cout << fnl;
36
    vector<vector<int>> visited(n * m, vector<int>(fnl, 1));
37
    queue<pair<pair<int, int>, int>> q;
38
    int ans = 0;
39
    q.push({{sx, sy}, 0});
40
    visited[sx * m + sy][0] = 0;
41
    while (!q.empty()) {
42
      ans++;
43
      int sz = q.size();
44
      while (sz--) {
45
        int x = q.front().first.first;
46
        int y = q.front().first.second;
47
        int bit = q.front().second;
48
        q.pop();
49
        for (int i = 0; i < 4; i++) {
50
          int nxtx = x + dirx[i];
51
          int nxty = y + diry[i];
52
          if (nxtx >= n || nxtx < 0 || nxty >= m || nxty < 0) continue;
53
          if (matrix[nxtx][nxty] == -8) continue;
54
          if (visited[nxtx * m + nxty][bit] == 0) continue;
55
          if (matrix[nxtx][nxty] < 0) {
56
            int lkidx = -1 * matrix[nxtx][nxty];
57
            if (bit & lock[lkidx]) {
58
              q.push({{nxtx, nxty}, bit});
59
              visited[nxtx * m + nxty][bit] = 0;
60
            }
61
          } else if (matrix[nxtx][nxty] == 0) {
62
            q.push({{nxtx, nxty}, bit});
63
            visited[nxtx * m + nxty][bit] = 0;
64
            continue;
65
          } else {
66
            int fbit = bit | matrix[nxtx][nxty];
67
            if (fbit == fnl) return ans;
68
            q.push({{nxtx, nxty}, fbit});
69
            visited[nxtx * m + nxty][fbit] = 0;
70
          }
71
        }
72
      }
73
    }
74
    return -1;
75
  }
76
};