最短路径遍历所有的节点 Shortest Path Visiting All Nodes

2018-10-06 22:04:38

问题描述：

问题求解：

对于边没有权重的最短路径的求解，首选的方案是bfs。

本题要求是求遍历所有节点的最短路径，由于本题中是没有要求一个节点只能访问一次的，也就是说可以访问一个节点多次，但是如果表征两次节点状态呢？可以使用（curNode， VisitedNode）来进行表征，如果两次的已经访问的节点相同那么就没有必要再进行访问了，最终的状态就是所有节点都访问过了。

另外，由于起点对结果是有影响的，因此在最开始需要将所有的节点都压栈。

    public int shortestPathLength(int[][] graph) {

        int n = graph.length;

        int target = (1 << n) - 1;

        Queue<Integer> q = new LinkedList<>();

        Set<Integer> seen = new HashSet<>();

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

            q.add(i << 16 | 1 << i);

            seen.add(i << 16 | 1 << i);

        }

        int step = 0;

        while (!q.isEmpty()) {

            int size = q.size();

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

                int cur = q.poll();

                int node = cur >> 16;

                int state = cur & 0xffff;

                if (state == target) return step;

                for (int next : graph[node]) {

                    int newstate = state | 1 << next;

                    if (seen.contains(next << 16 | newstate)) continue;

                    q.add(next << 16 | newstate);

                    seen.add(next << 16 | newstate);

                }

            }

            step += 1;

        }

        return -1;

    }

扩展：

864. Shortest Path to Get All Keys

问题描述：

问题求解：

给一个BFS模版。

    public int shortestPathAllKeys(String[] grid) {

        int m = grid.length;

        int n = grid[0].length();

        Queue<Integer> q = new LinkedList<>();

        HashSet<Integer> seen = new HashSet<>();

        int target = 0;

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

            for (int j = 0; j < n; j++) {

                char c = grid[i].charAt(j);

                if (c == '@') {

                    q.add(i << 16 | j << 8);

                    seen.add(i << 16 | j << 8);

                }

                if (c >= 'a' && c <= 'f') target |= 1 << (c - 'a');

            }

        }

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

        int step = 0;

        while (!q.isEmpty()) {

            int size = q.size();

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

                int cur = q.poll();

                int x = cur >> 16;

                int y = cur >> 8 & 0xFF;

                int key = cur & 0xFF;

                if (key == target) return step;

                for (int[] dir : dirs) {

                    int nx = x + dir[0];

                    int ny = y + dir[1];

                    int nkey = key;

                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;

                    char c = grid[nx].charAt(ny);

                    if (c == '#') continue;

                    if (c >= 'A' && c <= 'F' && ((key & (1 << (c - 'A'))) == 0)) continue;

                    if (c >= 'a' && c <= 'f') nkey = key | (1 << (c - 'a'));

                    int newstate = nx << 16 | ny << 8 | nkey;

                    if (seen.contains(newstate)) continue;

                    q.add(newstate);

                    seen.add(newstate);

                }

            }

            step += 1;

        }

        return -1;

    }

巴特西

最短路径遍历所有的节点 Shortest Path Visiting All Nodes

最新文章

热门文章