leetcode 864

864. Shortest path to find all keys

这道题难点在于要用一个class 来表示当前的状态，如果用普通的BFS来做的话，你会因为向外扩散的时候直接把所有的key全部放到当前bfs的范围里面了，但是这样是错误的，因为每条路径是单独的，所以要用一个class/object来表示，这样才能记录你每条路所得到的钥匙，然后通过bfs的特性来找到最短路径。这里用Set来存储每条路径的唯一性。而set里面用的数据结构是String，可能是因为更方便一点吧？因为"x + " " + y + " " + key"这种结构变成hash的话更方便，如果直接用set来存state可能要自己写hash function？key本身就是用数字来存储当前得到的钥匙的状态。这里用了bit mask，所以比较高级。但是本质上就是通过 key |= c - 'a' 来把当前钥匙记录下来，c = start.charAt(i*m+j) c就是当前节点的character
每次取出当前队列的State的时候，检查State cur.key == (1 << keyCount) - 1
这里1<<keyCount 是把1 向左移动keyCount次，这样减去1就能够得到所有key的表示方式，比如keyCount=3，那么1<<keyCount - 1 == 0111
就表示0， 1， 2号钥匙我们已经拿到手了。

class ShortestPathAllKeys {
    int[][] dirs = new int[][] {{0,1}, {0,-1}, {1,0}, {-1,0}};
    public int shortestPathAllKeys(String[] grid) {
        StringBuilder sb = new StringBuilder();
        int n = grid.length, m = grid[0].length(), keyCount = 0, lockCount = 0;
        // System.out.println("n: " + n + " m " + m);
        for (String s : grid) {
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c - 'a' >= 0 && c-'a' < 26) {
                    keyCount++;
                } else if (c - 'A' >= 0 && c - 'A' <= 25) {
                    lockCount++;
                }
            }
            sb.append(s);
        }
        String startStr = sb.toString();

        int start = startStr.indexOf('@');
        State startState = new State(start / m, start % m, 0);
        Queue<State> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.add(startState);
        visited.add(start / m + " " + start % m + " " + 0);
        int step = 0;
        while(!q.isEmpty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                State cur = q.poll();
                if (cur.key == (1 << keyCount) - 1) return step;
                for (int[] dir : dirs) {
                    int i = cur.x + dir[0], j = cur.y + dir[1], key = cur.key;
                    if (i >= 0 && i < n && j >= 0 && j < m && startStr.charAt(i*m+j) != '#') {
                        char c = startStr.charAt(i*m+j);
                        if (c - 'A' >= 0 && c - 'A' < 26) {
                            //it is a lock, check if we have the key
                            if ((key >> (c - 'A') & 1) == 0) {
                                continue;
                            }
                        } else if (c - 'a' >= 0 && c - 'a' < 26) {
                            // it is a key
                            key |= (1 << (c - 'a'));
                        }
                        if (visited.add(i + " " + j + " " + key)) q.add(new State(i, j, key));
                    }
                }
            }
            step++;
        }
        return -1;
    }
    class State {
        int x, y, key;
        public State(int x, int y, int key) {
            this.x = x;
            this.y = y;
            this.key = key;
        }
    }
}