1
class Solution {
2

3
  private static final int[][] DIRS = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
4

5
  public int shortestPathAllKeys(String[] grid) {
6
    int m = grid.length, n = grid[0].length();
7
    int numKeys = 0, startRow = -1, startCol = -1;
8

9
    for (int i = 0; i < m; i++) {
10
      for (int j = 0; j < n; j++) {
11
        char c = grid[i].charAt(j);
12

13
        if (isStart(c)) {
14
          startRow = i;
15
          startCol = j;
16
        } else if (isKey(c)) numKeys++;
17
      }
18
    }
19
    if (startRow == -1) return -1;
20

21
    int keyMask = (1 << numKeys) - 1;
22
    State start = new State(startRow, startCol, 0);
23
    Queue<State> queue = new LinkedList();
24
    Set<State> visited = new HashSet();
25
    int steps = 0;
26

27
    queue.offer(start);
28
    visited.add(start);
29

30
    while (!queue.isEmpty()) {
31
      int size = queue.size();
32

33
      while (size-- > 0) {
34
        int i = queue.peek().i;
35
        int j = queue.peek().j;
36
        int keys = queue.peek().keys;
37
        queue.poll();
38

39
        if (keys == keyMask) return steps;
40

41
        for (int[] dir : DIRS) {
42
          int di = i + dir[0];
43
          int dj = j + dir[1];
44
          int newKeys = keys;
45

46
          if (di < 0 || dj < 0 || di == m || dj == n) continue;
47

48
          char c = grid[di].charAt(dj);
49

50
          if (isWall(c)) continue;
51

52
          if (isLock(c) && !isKeyPresent(keys, c)) continue;
53

54
          if (isKey(c)) newKeys |= (1 << (c - 'a'));
55

56
          State newState = new State(di, dj, newKeys);
57

58
          if (visited.add(newState)) queue.offer(newState);
59
        }
60
      }
61
      steps++;
62
    }
63
    return -1;
64
  }
65

66
  private boolean isLock(char c) {
67
    return c >= 'A' && c <= 'Z';
68
  }
69

70
  private boolean isKey(char c) {
71
    return c >= 'a' && c <= 'z';
72
  }
73

74
  private boolean isWall(char c) {
75
    return c == '#';
76
  }
77

78
  private boolean isStart(char c) {
79
    return c == '@';
80
  }
81

82
  private boolean isKeyPresent(int keys, char lock) {
83
    return (keys & (1 << (lock - 'A'))) != 0;
84
  }
85
}
86

87
class State {
88
  public int i, j, keys;
89

90
  public State(int i, int j, int keys) {
91
    this.i = i;
92
    this.j = j;
93
    this.keys = keys;
94
  }
95

96
  @Override
97
  public boolean equals(Object obj) {
98
    if (!(obj instanceof State)) return false;
99
    State that = (State) obj;
100
    return i == that.i && j == that.j && keys == that.keys;
101
  }
102

103
  @Override
104
  public int hashCode() {
105
    int prime = 31;
106
    int hash = 1;
107
    hash = hash * prime + i;
108
    hash = hash * prime + j;
109
    hash = hash * prime + keys;
110
    return hash;
111
  }
112
}