|
| 1 | +/** |
| 2 | + * We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" |
| 3 | + * is the starting point, ("a", "b", ...) are keys, and ("A", "B", ...) are |
| 4 | + * locks. |
| 5 | + * |
| 6 | + * We start at the starting point, and one move consists of walking one space |
| 7 | + * in one of the 4 cardinal directions. We cannot walk outside the grid, or |
| 8 | + * walk into a wall. If we walk over a key, we pick it up. We can't walk over |
| 9 | + * a lock unless we have the corresponding key. |
| 10 | + * |
| 11 | + * For some 1 <= K <= 6, there is exactly one lowercase and one uppercase |
| 12 | + * letter of the first K letters of the English alphabet in the grid. This |
| 13 | + * means that there is exactly one key for each lock, and one lock for each |
| 14 | + * key; and also that the letters used to represent the keys and locks were |
| 15 | + * chosen in the same order as the English alphabet. |
| 16 | + * |
| 17 | + * Return the lowest number of moves to acquire all keys. |
| 18 | + * If it's impossible, return -1. |
| 19 | + * |
| 20 | + * Example 1: |
| 21 | + * Input: ["@.a.#","###.#","b.A.B"] |
| 22 | + * Output: 8 |
| 23 | + * |
| 24 | + * Example 2: |
| 25 | + * Input: ["@..aA","..B#.","....b"] |
| 26 | + * Output: 6 |
| 27 | + * |
| 28 | + * Note: |
| 29 | + * 1 <= grid.length <= 30 |
| 30 | + * 1 <= grid[0].length <= 30 |
| 31 | + * grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F' |
| 32 | + * The number of keys is in [1, 6]. |
| 33 | + * Each key has a different letter and opens exactly one lock. |
| 34 | + */ |
| 35 | + |
| 36 | +publicclassShortestPathToGetAllKeys864 { |
| 37 | +privateint[][]directions =newint[][]{{0,1}, {1,0}, {0, -1}, {-1,0}}; |
| 38 | + |
| 39 | +publicintshortestPathAllKeys(String[]grid) { |
| 40 | +intM =grid.length; |
| 41 | +intN =grid[0].length(); |
| 42 | +char[][]maze =newchar[M][N]; |
| 43 | +intnumKeys =0; |
| 44 | +int[]start =newint[2]; |
| 45 | +for (inti=0;i<M;i++) { |
| 46 | +char[]row =grid[i].toCharArray(); |
| 47 | +for (intj=0;j<N;j++) { |
| 48 | +maze[i][j] =row[j]; |
| 49 | +if (row[j] =='@') { |
| 50 | +start[0] =i; |
| 51 | +start[1] =j; |
| 52 | + }elseif (row[j] >='a' &&row[j] <='f') { |
| 53 | +numKeys++; |
| 54 | + } |
| 55 | + } |
| 56 | + } |
| 57 | + |
| 58 | +int[]res =newint[]{Integer.MAX_VALUE}; |
| 59 | +Set<Character>keySet =newHashSet<>(); |
| 60 | +helper(maze,start,numKeys,keySet,0,M,N,res); |
| 61 | +returnres[0] ==Integer.MAX_VALUE ? -1 :res[0]; |
| 62 | + } |
| 63 | + |
| 64 | +publicvoidhelper(char[][]maze,int[]start,intnumKeys,Set<Character>keySet,intsteps,intM,intN,int[]res) { |
| 65 | +if (numKeys ==keySet.size()) { |
| 66 | +res[0] =Math.min(res[0],steps); |
| 67 | +return; |
| 68 | + } |
| 69 | +boolean[][]visited =newboolean[M][N]; |
| 70 | +Queue<int[]>q =newLinkedList<>(); |
| 71 | +q.add(start); |
| 72 | +visited[start[0]][start[1]] =true; |
| 73 | +Set<int[]>newKeys =newHashSet<>(); |
| 74 | +intlevel =1; |
| 75 | +while (!q.isEmpty() &&steps +level <res[0]) { |
| 76 | +intsize =q.size(); |
| 77 | +for (inti=0;i<size;i++) { |
| 78 | +int[]curr =q.poll(); |
| 79 | +for (int[]dir:directions) { |
| 80 | +intx =curr[0] +dir[0]; |
| 81 | +inty =curr[1] +dir[1]; |
| 82 | +if (x <0 ||y <0 ||x >=M ||y >=N)continue; |
| 83 | +charnext =maze[x][y]; |
| 84 | +if (next =='#' ||visited[x][y])continue; |
| 85 | +if (next =='@' ||next =='.') { |
| 86 | +q.add(newint[]{x,y}); |
| 87 | +visited[x][y] =true; |
| 88 | + }elseif (next >='a' &&next <='f') { |
| 89 | +if (!keySet.contains(next)) { |
| 90 | +newKeys.add(newint[]{x,y,level}); |
| 91 | + }else { |
| 92 | +q.add(newint[]{x,y}); |
| 93 | +visited[x][y] =true; |
| 94 | + } |
| 95 | + }elseif (next >='A' &&next <='F') { |
| 96 | +if (keySet.contains(Character.toLowerCase(next))) { |
| 97 | +q.add(newint[]{x,y}); |
| 98 | +visited[x][y] =true; |
| 99 | + } |
| 100 | + } |
| 101 | + } |
| 102 | + } |
| 103 | +level++; |
| 104 | + } |
| 105 | + |
| 106 | +if (!newKeys.isEmpty()) { |
| 107 | +for (int[]newKey:newKeys) { |
| 108 | +int[]newKeyPos =newint[]{newKey[0],newKey[1]}; |
| 109 | +charkey =maze[newKey[0]][newKey[1]]; |
| 110 | +keySet.add(key); |
| 111 | +helper(maze,newKeyPos,numKeys,keySet,steps +newKey[2],M,N,res); |
| 112 | +keySet.remove(key); |
| 113 | + } |
| 114 | + } |
| 115 | + } |
| 116 | + |
| 117 | +} |