获取所有key的最短路径-数据结构与算法(中)

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

难度:
Hard

题意：

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

思路：

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

代码：

```java
class Solution {
    private int[] dx = new int[]{1, -1, 0, 0};
    private int[] dy = new int[]{0, 0, 1, -1};

private class State {
        int setKey;
        int setLock;
        int posX;
        int posY;

public State() {
        }

public State(int setKey, int setLock, int posX, int posY) {
            this.setKey = setKey;
            this.setLock = setLock;
            this.posX = posX;
            this.posY = posY;
        }

@Override
        public int hashCode() {
            int hashCode = 0;
            hashCode = hashCode * 31 + Integer.hashCode(setKey);
            hashCode = hashCode * 31 + Integer.hashCode(setLock);
            hashCode = hashCode * 31 + Integer.hashCode(posX);
            hashCode = hashCode * 31 + Integer.hashCode(posY);
            return hashCode;
        }

@Override
        public boolean equals(Object obj) {
            if (!(obj instanceof State)) {
                return false;
            }
            State state = (State) obj;
            return setKey == state.setKey && setLock == state.setLock &&
                    posX == state.posX && posY == state.posY;
        }
    }

private class Point {
        int x;
        int y;

public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

public int shortestPathAllKeys(String[] grid) {
        Map<State, Integer> currentMap = new HashMap<State, Integer>();
        State start = new State();
        int numKey = 0;
        for (int i = 0;i < grid.length;i++) {
            for (int j = 0;j < grid[i].length();j++) {
                if (grid[i].charAt(j) == '@') {
                    start.posX = i;
                    start.posY = j;
                }
                if (grid[i].charAt(j) <= 'f' && grid[i].charAt(j) >= 'a') {
                    numKey ++;
                }
            }
        }
        start.setKey = start.setLock = ((1 << numKey) - 1);
        currentMap.put(start, 0);
        if (numKey == 0) {
            return 0;
        }

int ret = 0x3fffffff;
        while (!currentMap.isEmpty()) {
            Map<State, Integer> nextMap = new HashMap<State, Integer>();

for (State state: currentMap.keySet()) {

int curValue = currentMap.get(state);
                if (state.setKey == 0) {
                    ret = ret < curValue ? ret : curValue;
                    continue;
                }

int[][] dis = new int[grid.length][grid[0].length()];
                for (int i = 0;i < grid.length;i++) {
                    for (int j = 0;j < grid[0].length();j++) {
                        dis[i][j] = 0x3fffffff;
                    }
                }
                dis[state.posX][state.posY] = 0;
                LinkedList<Point> queue = new LinkedList<Point>();
                queue.addLast(new Point(state.posX, state.posY));
                while (!queue.isEmpty()) {
                    Point point = queue.pollFirst();
                    for (int i = 0;i < 4;i++) {
                        Point next = new Point(point.x + dx[i], point.y + dy[i]);
                        if (next.x < 0 || next.y < 0 || next.x >= grid.length || next.y >= grid[0].length()) {
                            continue;
                        }
                        char c = grid[next.x].charAt(next.y);
                        if (c == '#') {
                            continue;
                        }
                        if (c <= 'F' && c >= 'A' && (state.setKey & (1 << (c - 'A'))) != 0) {
                            continue;
                        }

if (dis[next.x][next.y] == 0x3fffffff) {
                            dis[next.x][next.y] = dis[point.x][point.y] + 1;
                            queue.addLast(next);

if (c <= 'f' && c >= 'a' && (state.setKey & (1 << (c - 'a'))) != 0) {
                                State nextState = new State(
                                        state.setKey - (1 << (c - 'a')),
                                        state.setLock,
                                        next.x,
                                        next.y
                                );
                                int value = currentMap.get(state) + dis[next.x][next.y];
                                if (!nextMap.containsKey(nextState) || value < nextMap.get(nextState)) {
                                    nextMap.put(nextState, value);
                                }
                            }

if (c <= 'F' && c >= 'A' && (state.setLock & (1 << (c - 'A'))) != 0) {
                                State nextState = new State(
                                        state.setKey,
                                        state.setLock - (1 << (c - 'A')),
                                        next.x,
                                        next.y
                                );
                                int value = curValue + dis[next.x][next.y];
                                if (!nextMap.containsKey(nextState) || value < nextMap.get(nextState)) {
                                    nextMap.put(nextState, value);
                                }
                            }
                        }
                    }
                }
            }

currentMap = nextMap;
        }
        if (ret == 0x3fffffff) {
            return -1;
        } else {
            return ret;
        }
    }
}
```

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

编程之道-算法面试(下)

算法面试通关 50 讲

业务开发实用算法精讲

数据结构与算法(下)

数据结构与算法(上)

编程之道-算法面试(上)

数据结构与算法之美