LeetCode 864 - Shortest Path to Get All Keys

https://leetcode.com/problems/shortest-path-to-get-all-keys/

We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", ...) are keys, and ("A", "B", ...) are locks.

We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions.  We cannot walk outside the grid, or walk into a wall.  If we walk over a key, we pick it up.  We can't walk over a lock unless we have the corresponding key.

For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid.  This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys.  If it's impossible, return -1.

Example 1:

Input: ["@.a.#","###.#","b.A.B"]
Output: 8

Example 2:

Input: ["@..aA","..B#.","....b"]
Output: 6

https://www.jianshu.com/p/7d8a3ecc536b

迷宫遍历 + 最少步数 = BFS
注意 状态的表示即可，这里我使用了三维数组表示状态(x坐标，y坐标，身上携带的钥匙串)
内存开销是 地图大小*钥匙串 = 31 * 31 * (1<<6) a-f 6把钥匙
☝️一个技巧：使用 位运算 异或判断 身上钥匙串是否有对应的钥匙，比较方便

https://jxy370.com/index.php/2018/08/23/leetcode-864/

求最短路径第一反应就是应该是广度优先搜索，但是由于门的存在，首先寻找哪些药匙就是一个需要解决的问题，而且找到一个钥匙之后有时还需要重走走过的路回到门的地方，用普通的二维广度优先搜索显然是不行的。

找到的方法非常巧妙，其将各个钥匙的获得状态转换为二进制编码，则可以用一个6位的二进制数即小于128的数来表示状态，然后就可以将二维的搜索转换为三维，即找到某个钥匙后，获得钥匙状态改变，就可以在另一状态下继续遍历迷宫，可以以不同状态重走走过的路。

需要注意的点是，起点也是可以通过的。

https://leetcode.com/problems/shortest-path-to-get-all-keys/discuss/147696/Java-23ms-BFS-solution

This is a typical BFS shortest distance problem. The key point here is how to represent the status for each move. I use the current key we have and the position to represent the status. Also, to avoid unnecessary search, I use a nested array dist[key][i][j], which represents the distance from starting point to current status(key, i, j).

    class Status {
        int key, i, j;
        public Status(int key, int i, int j) {
            this.key = key;
            this.i = i;
            this.j = j;
        }
    }
    
    public int shortestPathAllKeys(String[] grid) {
        int success = 0, startI = 0, startJ = 0, rows = grid.length, cols = grid[0].length();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char c = grid[i].charAt(j);
                if (c >= 'A' && c <= 'F') {
                    success |= 1 << (c - 'A');
                }
                
                if (c == '@') {
                    startI = i;
                    startJ = j;
                }
            }
        }
        int[][][] dist = new int[1 << 6][rows][cols];
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist[0].length; j++) {
                for (int k = 0; k < dist[0][0].length; k++) {
                    dist[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }
        Queue<Status> queue = new LinkedList<>();
        queue.offer(new Status(0, startI, startJ));
        dist[0][startI][startJ] = 0;
        int path = 0;
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Status status = queue.poll();
                int key = status.key, x = status.i, y = status.j;
                if (key == success) return path;
                for (int[] dir : dirs) {
                    int xx = x + dir[0], yy = y + dir[1];
                    if (xx >= 0 && xx < rows && yy >= 0 && yy < cols && grid[xx].charAt(yy) != '#') {
                        int nextKey = key;
                        char c = grid[xx].charAt(yy);
                        if (c >= 'a' && c <= 'f') {
                            nextKey = key | (1 << (c - 'a'));
                        }
                        
                        if (c >= 'A' && c <= 'F') {
                            if ((nextKey & (1 << (c - 'A'))) == 0) continue;
                        }
                        
                        if (path + 1 < dist[nextKey][xx][yy]) {
                            dist[nextKey][xx][yy] = path + 1;
                            queue.offer(new Status(nextKey, xx, yy));
                        }
                    }
                }
            }
            path++;
        }
        return -1;
    }

https://leetcode.com/problems/shortest-path-to-get-all-keys/discuss/146878/Java-BFS-Solution

1. Use Bit to represent the keys.
2. Use State to represent visited states.

class Solution {
    class State {
        int keys, i, j;
        State(int keys, int i, int j) {
            this.keys = keys;
            this.i = i;
            this.j = j;
        }
    }
    public int shortestPathAllKeys(String[] grid) {
        int x = -1, y = -1, m = grid.length, n = grid[0].length(), max = -1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') {
                    x = i;
                    y = j;
                }
                if (c >= 'a' && c <= 'f') {
                    max = Math.max(c - 'a' + 1, max);
                }
            }
        }
        State start = new State(0, x, y);
        Queue<State> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        visited.add(0 + " " + x + " " + y);
        q.offer(start);
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                State cur = q.poll();
                if (cur.keys == (1 << max) - 1) {
                    return step;
                }
                for (int[] dir : dirs) {
                    int i = cur.i + dir[0];
                    int j = cur.j + dir[1];
                    int keys = cur.keys;
                    if (i >= 0 && i < m && j >= 0 && j < n) {
                        char c = grid[i].charAt(j);
                        if (c == '#') {
                            continue;
                        }
                        if (c >= 'a' && c <= 'f') {
                            keys |= 1 << (c - 'a');
                        }
                        if (c >= 'A' && c <= 'F' && ((keys >> (c - 'A')) & 1) == 0) {
                            continue;
                        }
                        if (!visited.contains(keys + " " + i + " " + j)) {
                            visited.add(keys + " " + i + " " + j);
                            q.offer(new State(keys, i, j));
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }




Approach 2: Points of Interest + Dijkstra

Clearly, we only really care about walking between points of interest: the keys, locks, and starting position. We can use this insight to speed up our calculation.

Let's make this intuition more formal: any walk can be decomposed into primitive segments, where each segment (between two points of interest) is primitive if and only if it doesn't touch any other point of interest in between.

Then, we can calculate the distance (of a primitive segment) between any two points of interest, using a breadth first search.

Afterwards, we have some graph (where each node refers to at most $13$ places, and at most $2^6$ states of keys). We have a starting node (at '@' with no keys) and ending nodes (at anywhere with all keys.) We also know all the costs to go from one node to another - each node has outdegree at most 13. This shortest path problem is now ideal for using Dijkstra's algorithm.

Dijkstra's algorithm uses a priority queue to continually searches the path with the lowest cost to destination, so that when we reach the target, we know it must have been through the lowest cost path. Refer to this link for more detail.

Again, each part of the algorithm is relatively straightforward (for those familiar with BFS and Dijkstra's algorithm), but the implementation in total can be quite challenging.

• Time Complexity: $O(RC(2\mathcal{A} + 1) + \mathcal{E} \log \mathcal{N})$, where $R, C$ are the dimensions of the grid, and $\mathcal{A}$ is the maximum number of keys, $\mathcal{N} = (2\mathcal{A} + 1) * 2^\mathcal{A}$ is the number of nodes when we perform Dijkstra's, and $\mathcal{E} = \mathcal{N} * (2 \mathcal{A} + 1)$ is the maximum number of edges.
• Space Complexity: $O(\mathcal{N})$. 

    int INF = Integer.MAX_VALUE;

    String[] grid;

    int R, C;

    Map<Character, Point> location;

    int[] dr = new int[]{-1, 0, 1, 0};

    int[] dc = new int[]{0, -1, 0, 1};

    public int shortestPathAllKeys(String[] grid) {

        this.grid = grid;

        R = grid.length;

        C = grid[0].length();

        //location : the points of interest

        location = new HashMap();

        for (int r = 0; r < R; ++r)

            for (int c = 0; c < C; ++c) {

                char v = grid[r].charAt(c);

                if (v != '.' && v != '#')

                    location.put(v, new Point(r, c));

            }

        int targetState = (1 << (location.size() / 2)) - 1;

        Map<Character, Map<Character, Integer>> dists = new HashMap();

        for (char place: location.keySet())

            dists.put(place, bfsFrom(place));

        //Dijkstra

        PriorityQueue<ANode> pq = new PriorityQueue<ANode>((a, b) ->

                Integer.compare(a.dist, b.dist));

        pq.offer(new ANode(new Node('@', 0), 0));

        Map<Node, Integer> finalDist = new HashMap();

        finalDist.put(new Node('@', 0), 0);

        while (!pq.isEmpty()) {

            ANode anode = pq.poll();

            Node node = anode.node;

            int d = anode.dist;

            if (finalDist.getOrDefault(node, INF) < d) continue;

            if (node.state == targetState) return d;

            for (char destination: dists.get(node.place).keySet()) {

                int d2 = dists.get(node.place).get(destination);

                int state2 = node.state;

                if (Character.isLowerCase(destination)) //key

                    state2 |= (1 << (destination - 'a'));

                if (Character.isUpperCase(destination)) //lock

                    if ((node.state & (1 << (destination - 'A'))) == 0) // no key

                        continue;

                if (d + d2 < finalDist.getOrDefault(new Node(destination, state2), INF)) {

                    finalDist.put(new Node(destination, state2), d + d2);

                    pq.offer(new ANode(new Node(destination, state2), d+d2));

                }

            }

        }

        return -1;

    }

    public Map<Character, Integer> bfsFrom(char source) {

        int sr = location.get(source).x;

        int sc = location.get(source).y;

        boolean[][] seen = new boolean[R][C];

        seen[sr][sc] = true;

        int curDepth = 0;

        Queue<Point> queue = new LinkedList();

        queue.offer(new Point(sr, sc));

        queue.offer(null);

        Map<Character, Integer> dist = new HashMap();

        while (!queue.isEmpty()) {

            Point p = queue.poll();

            if (p == null) {

                curDepth++;

                if (!queue.isEmpty())

                    queue.offer(null);

                continue;

            }

            int r = p.x, c = p.y;

            if (grid[r].charAt(c) != source && grid[r].charAt(c) != '.') {

                dist.put(grid[r].charAt(c), curDepth);

                continue; // Stop walking from here if we reach a point of interest

            }

            for (int i = 0; i < 4; ++i) {

                int cr = r + dr[i];

                int cc = c + dc[i];

                if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){

                    if (grid[cr].charAt(cc) != '#') {

                        queue.offer(new Point(cr, cc));

                        seen[cr][cc] = true;

                    }

                }

            }

        }

        return dist;

    }

}

// ANode: Annotated Node

class ANode {

    Node node;

    int dist;

    ANode(Node n, int d) {

        node = n;

        dist = d;

    }

}

class Node {

    char place;

    int state;

    Node(char p, int s) {

        place = p;

        state = s;

    }

    @Override

    public boolean equals(Object o) {

        if (this == o) return true;

        if (!(o instanceof Node)) return false;

        Node other = (Node) o;

        return (place == other.place && state == other.state);

    }

    @Override

    public int hashCode() {

        return 256 * state + place;

    }

}

X. Approach 1: Brute Force + Permutations

http://hehejun.blogspot.com/2018/07/leetcodeshortest-path-to-get-all-keys.html

这是一道最短路径的问题，但是特殊的地方在于只有我们到达某一些点之后才能解锁对应的其他的点。所以普通的最短路径的算法是不行的，需要进行一定的修改。在那之前，brute force的算法是很容易想到的，因为我们的目的是取得所有的锁，锁最多也就6个，我们可以枚举所有序列的permutation。比如我们只有三把锁，我们枚举的序列为：

• abc
• acb
• bac
• bca
• cab
• cba

对于每一个枚举的序列，比如abc，我们依次计算a到b和b到c的最短距离，用bfs计算即可。注意每一次拿到钥匙之后要解锁对应的部分即可。假设输入的矩阵为m x n，锁的数目为k，那么permutation的数量有k!个，序列的长度为k，所以我们一共要进行k * k次bfs，每一次的时间复杂度为O(m * n),所以总的时间复杂度为O(m * n * k * k!)

We have to pick up the keys $K$ in some order, say $K_{\sigma_i}$.

For each ordering, let's do a breadth first search to find the distance to the next key.

For example, if the keys are 'abcdef', then for each ordering such as 'bafedc', we will try to calculate the candidate distance from '@' -> 'b' -> 'a' -> 'f' -> 'e' -> 'd' -> 'c'.

Between each segment of our path (and corresponding breadth-first search), we should remember what keys we've picked up. Keys that are picked up become part of a mask that helps us identify what locks we are allowed to walk through during the next breadth-first search.

Each part of the algorithm is relatively straightforward, but the implementation in total can be quite challenging. See the comments for more details.

• Time Complexity: $O(R * C * \mathcal{A} * \mathcal{A}!)$, where $R, C$ are the dimensions of the grid, and $\mathcal{A}$ is the maximum number of keys ($\mathcal{A}$ because it is the "size of the alphabet".) Each bfs is performed up to $\mathcal{A} * \mathcal{A}!$ times.
• Space Complexity: $O(R * C + \mathcal{A}!)$, the space for the bfs and to store the candidate key permutations. 

  int INF = Integer.MAX_VALUE;

  String[] grid;

  int R, C;

  Map<Character, Point> location;

  int[] dr = new int[] { -1, 0, 1, 0 };

  int[] dc = new int[] { 0, -1, 0, 1 };

  public int shortestPathAllKeys(String[] grid) {

    this.grid = grid;

    R = grid.length;

    C = grid[0].length();

    // location['a'] = the coordinates of 'a' on the grid, etc.

    location = new HashMap();

    for (int r = 0; r < R; ++r)

      for (int c = 0; c < C; ++c) {

        char v = grid[r].charAt(c);

        if (v != '.' && v != '#')

          location.put(v, new Point(r, c));

      }

    int ans = INF;

    int num_keys = location.size() / 2;

    String[] alphabet = new String[num_keys];

    for (int i = 0; i < num_keys; ++i)

      alphabet[i] = Character.toString((char) ('a' + i));

    // alphabet = ["a", "b", "c"], if there were 3 keys

    search: for (String cand : permutations(alphabet, 0, num_keys)) {

      // bns : the built candidate answer, consisting of the sum

      // of distances of the segments from '@' to cand[0] to cand[1] etc.

      int bns = 0;

      for (int i = 0; i < num_keys; ++i) {

        char source = i > 0 ? cand.charAt(i - 1) : '@';

        char target = cand.charAt(i);

        // keymask : an integer with the 0-th bit set if we picked up

        // key 'a', the 1-th bit set if we picked up key 'b', etc.

        int keymask = 0;

        for (int j = 0; j < i; ++j)

          keymask |= 1 << (cand.charAt(j) - 'a');

        int d = bfs(source, target, keymask);

        if (d == INF)

          continue search;

        bns += d;

        if (bns >= ans)

          continue search;

      }

      ans = bns;

    }

    return ans < INF ? ans : -1;

  }

  public int bfs(char source, char target, int keymask) {

    int sr = location.get(source).x;

    int sc = location.get(source).y;

    int tr = location.get(target).x;

    int tc = location.get(target).y;

    boolean[][] seen = new boolean[R][C];

    seen[sr][sc] = true;

    int curDepth = 0;

    Queue<Point> queue = new LinkedList();

    queue.offer(new Point(sr, sc));

    queue.offer(null);

    while (!queue.isEmpty()) {

      Point p = queue.poll();

      if (p == null) {

        curDepth++;

        if (!queue.isEmpty())

          queue.offer(null);

        continue;

      }

      int r = p.x, c = p.y;

      if (r == tr && c == tc)

        return curDepth;

      for (int i = 0; i < 4; ++i) {

        int cr = r + dr[i];

        int cc = c + dc[i];

        if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]) {

          char cur = grid[cr].charAt(cc);

          if (cur != '#') {

            if (Character.isUpperCase(cur) && (((1 << (cur - 'A')) & keymask) <= 0))

              continue; // at lock and don't have key

            queue.offer(new Point(cr, cc));

            seen[cr][cc] = true;

          }

        }

      }

    }

    return INF;

  }

  public List<String> permutations(String[] alphabet, int used, int size) {

    List<String> ans = new ArrayList();

    if (size == 0) {

      ans.add(new String(""));

      return ans;

    }

    for (int b = 0; b < alphabet.length; ++b)

      if (((used >> b) & 1) == 0)

        for (String rest : permutations(alphabet, used | (1 << b), size - 1))

          ans.add(alphabet[b] + rest);

    return ans;

  }