当前位置:  首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意:

  1. 给一个最大30*30的地图
  2. 其中有6个钥匙6个锁,锁要拿到相应的钥匙才能开
  3. 上下左右四个方向走,问最少要走多少步,才能拿到所有的钥匙

思路:

  • 这个题比较暴力,就是广度优先搜索
  • 注意搜索空间,总共最多才6个钥匙6个锁,定义状态为:去过的钥匙集合(二进制压缩),去过的锁集合(二进制压缩),当前位置。我们需要从这个状态转移到另一个状态,从这个状态开始广度优先搜索。转移到另一个状态,合并下一轮的搜索空间
  • 复杂度是o(k 2 ^ 6 2 ^ 6 30 30),k是搜索空间所用数据结构的复杂度
  • 这个题我写的比较差,主要是用了哈希表来保存搜索空间,引入了不必要的复杂度,超时了。大家写的时候直接用数组来保存搜索空间即可
  • 这道题优化空间很大,可以剪枝,大家可以当做练习

代码:

  1. class Solution {
  2. private int[] dx = new int[]{1, -1, 0, 0};
  3. private int[] dy = new int[]{0, 0, 1, -1};
  4. private class State {
  5. int setKey;
  6. int setLock;
  7. int posX;
  8. int posY;
  9. public State() {
  10. }
  11. public State(int setKey, int setLock, int posX, int posY) {
  12. this.setKey = setKey;
  13. this.setLock = setLock;
  14. this.posX = posX;
  15. this.posY = posY;
  16. }
  17. @Override
  18. public int hashCode() {
  19. int hashCode = 0;
  20. hashCode = hashCode * 31 + Integer.hashCode(setKey);
  21. hashCode = hashCode * 31 + Integer.hashCode(setLock);
  22. hashCode = hashCode * 31 + Integer.hashCode(posX);
  23. hashCode = hashCode * 31 + Integer.hashCode(posY);
  24. return hashCode;
  25. }
  26. @Override
  27. public boolean equals(Object obj) {
  28. if (!(obj instanceof State)) {
  29. return false;
  30. }
  31. State state = (State) obj;
  32. return setKey == state.setKey && setLock == state.setLock &&
  33. posX == state.posX && posY == state.posY;
  34. }
  35. }
  36. private class Point {
  37. int x;
  38. int y;
  39. public Point(int x, int y) {
  40. this.x = x;
  41. this.y = y;
  42. }
  43. }
  44. public int shortestPathAllKeys(String[] grid) {
  45. Map<State, Integer> currentMap = new HashMap<State, Integer>();
  46. State start = new State();
  47. int numKey = 0;
  48. for (int i = 0;i < grid.length;i++) {
  49. for (int j = 0;j < grid[i].length();j++) {
  50. if (grid[i].charAt(j) == '@') {
  51. start.posX = i;
  52. start.posY = j;
  53. }
  54. if (grid[i].charAt(j) <= 'f' && grid[i].charAt(j) >= 'a') {
  55. numKey ++;
  56. }
  57. }
  58. }
  59. start.setKey = start.setLock = ((1 << numKey) - 1);
  60. currentMap.put(start, 0);
  61. if (numKey == 0) {
  62. return 0;
  63. }
  64. int ret = 0x3fffffff;
  65. while (!currentMap.isEmpty()) {
  66. Map<State, Integer> nextMap = new HashMap<State, Integer>();
  67. for (State state: currentMap.keySet()) {
  68. int curValue = currentMap.get(state);
  69. if (state.setKey == 0) {
  70. ret = ret < curValue ? ret : curValue;
  71. continue;
  72. }
  73. int[][] dis = new int[grid.length][grid[0].length()];
  74. for (int i = 0;i < grid.length;i++) {
  75. for (int j = 0;j < grid[0].length();j++) {
  76. dis[i][j] = 0x3fffffff;
  77. }
  78. }
  79. dis[state.posX][state.posY] = 0;
  80. LinkedList<Point> queue = new LinkedList<Point>();
  81. queue.addLast(new Point(state.posX, state.posY));
  82. while (!queue.isEmpty()) {
  83. Point point = queue.pollFirst();
  84. for (int i = 0;i < 4;i++) {
  85. Point next = new Point(point.x + dx[i], point.y + dy[i]);
  86. if (next.x < 0 || next.y < 0 || next.x >= grid.length || next.y >= grid[0].length()) {
  87. continue;
  88. }
  89. char c = grid[next.x].charAt(next.y);
  90. if (c == '#') {
  91. continue;
  92. }
  93. if (c <= 'F' && c >= 'A' && (state.setKey & (1 << (c - 'A'))) != 0) {
  94. continue;
  95. }
  96. if (dis[next.x][next.y] == 0x3fffffff) {
  97. dis[next.x][next.y] = dis[point.x][point.y] + 1;
  98. queue.addLast(next);
  99. if (c <= 'f' && c >= 'a' && (state.setKey & (1 << (c - 'a'))) != 0) {
  100. State nextState = new State(
  101. state.setKey - (1 << (c - 'a')),
  102. state.setLock,
  103. next.x,
  104. next.y
  105. );
  106. int value = currentMap.get(state) + dis[next.x][next.y];
  107. if (!nextMap.containsKey(nextState) || value < nextMap.get(nextState)) {
  108. nextMap.put(nextState, value);
  109. }
  110. }
  111. if (c <= 'F' && c >= 'A' && (state.setLock & (1 << (c - 'A'))) != 0) {
  112. State nextState = new State(
  113. state.setKey,
  114. state.setLock - (1 << (c - 'A')),
  115. next.x,
  116. next.y
  117. );
  118. int value = curValue + dis[next.x][next.y];
  119. if (!nextMap.containsKey(nextState) || value < nextMap.get(nextState)) {
  120. nextMap.put(nextState, value);
  121. }
  122. }
  123. }
  124. }
  125. }
  126. }
  127. currentMap = nextMap;
  128. }
  129. if (ret == 0x3fffffff) {
  130. return -1;
  131. } else {
  132. return ret;
  133. }
  134. }
  135. }

该分类下的相关小册推荐: