3、BFS &迷宫问题&八数码

AcWing 844. 走迷宫

AcWing 845. 八数码

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.migon();
    }

    int N = 1010;
    int n, m;
    int[][] g = new int[N][N];//g存储地图的0/1
    int[][] d = new int[N][N];//d表示到(0,0)的距离
    Queue<Point> queue = new LinkedTransferQueue<>();

    class Point implements Comparable {
        int x, y;

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

        @Override
        public int compareTo(Object o) {
            return 0;
        }
    }

    int bfs() {
        d[0][0] = 0;
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, 1, 0, -1};
        //移动的方向
        queue.offer(new Point(0, 0));

        //因为是按层数搜索，第一次搜到的一定最短
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int pos_x = point.x;
            int pos_y = point.y;
            for (int i = 0; i < 4; i++) {
                int try_x = pos_x + dx[i];
                int try_y = pos_y + dy[i];
                if (try_x >= 0 && try_x < n && try_y >= 0 && try_y < m && g[try_x][try_y] == 0&&d[try_x][try_y] == -1) {
                    d[try_x][try_y] = d[pos_x][pos_y] + 1;
                    queue.offer(new Point(try_x, try_y));
                }
            }
        }
        return d[n - 1][m - 1];
    }

    void migon() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < N; i++) {
            Arrays.fill(d[i], -1);//表示到（0，0）不可达
        }
        System.out.println(bfs());
    }
}

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.bashuma();
    }

    int bfs(String start) {
        String end = "12345678x";
        Queue<String> queue = new LinkedTransferQueue();
        HashMap<String, Integer> hashMap = new HashMap();
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, 1, 0, -1};
        //移动的方向
        queue.offer(start);
        hashMap.put(start, 0);
        while (!queue.isEmpty()) {
            String state = queue.poll();
            int old_pos = state.lastIndexOf("x");
            int old_x = old_pos / 3;
            int old_y = old_pos % 3;
            for (int i = 0; i < 4; i++) {
                int new_x = old_x + dx[i];
                int new_y = old_y + dy[i];
                int new_pos = new_x * 3 + new_y;
                String old_state = state;
                if (new_x >= 0 && new_x < 3 && new_y >= 0 && new_y < 3) {
                    String temp = swapString(state, old_pos, new_pos);
                    if (!hashMap.containsKey(temp)) {
                        state = temp;
                        queue.add(state);
                        hashMap.put(state, hashMap.get(old_state) + 1);
                        state = swapString(state, old_pos, new_pos);
                    }
                }
            }
        }
        //hashmap在bfs完后，不一定可以找到含有end的一条路径
        if (hashMap.containsKey(end)) {
            return hashMap.get(end);
        } else {
            return -1;
        }
    }

    String swapString(String s, int x, int y) {
        char[] ss = s.toCharArray();
        char temp = ss[x];
        ss[x] = ss[y];
        ss[y] = temp;
        String res = "";
        for (int i = 0; i < ss.length; i++) {
            res += ss[i];
        }
        return res;
    }

    void bashuma() {
        Scanner sc = new Scanner(System.in);
        String start = sc.nextLine();
        start = start.replace(" ", "");
        System.out.println(bfs(start));
    }
}