本文最后更新于2021年11月3日,已超过 1 个月没更新!

第三讲 搜索与图论

DFS

排列数字

import java.util.*;

public class Main{
    static int[] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        visited = new int[n];
        for (int i = 0; i < n; ++ i) nums[i] = i + 1;
        List<List<Integer>> ans = new LinkedList<>();
        dfs(nums, new LinkedList<Integer>(), ans);
        for (List<Integer> list : ans) {
            for (int num : list) {
                System.out.print (num + " ");
            }
            System.out.println();
        }
    }

    public static void dfs (int[] nums, List<Integer> list, List<List<Integer>> ans) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; ++ i) {
            if (visited[i] == 1) continue;
            list.add(nums[i]);
            visited[i] = 1;
            dfs(nums, list, ans);
            visited[i] = 0;
            list.remove(list.size() - 1);
        }
    }
}

n-皇后问题

🍉 第一种搜索顺序(最优)

import java.util.*;

public class Main{
    static int N = 10;
    static char[][] g = new char[N][N];
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[N * 2];
    static boolean[] udg = new boolean[N * 2];
    static int n;
    public static void dfs (int u) {
        if (u == n) {
            for (int i = 0; i < n; ++ i) {
                for (int j = 0; j < n; ++ j) System.out.print(g[i][j]);
                System.out.println();
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; ++ i) {
            if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
                g[u][i] = 'Q';
                col[i] = dg[u + i] = udg[n - u + i] = true;
                dfs(u + 1);
                col[i] = dg[u + i] = udg[n - u + i] = false;
                g[u][i] = '.';
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0 ; i< n; ++ i)
            for (int j = 0; j < n; ++ j) g[i][j] = '.';

        dfs(0);
        return;
    }
}

🍉 第二种搜索顺序 (原始搜索顺序 顺序枚举)

import java.util.*;

public class Main{
    static int N = 10;
    static boolean[] col = new boolean[N];
    static boolean[] row = new boolean[N];
    static boolean[] dg = new boolean[N * 2];
    static boolean[] udg = new boolean[N * 2];

    static int n;
    static char[][] g;

    public static void dfs (int x, int y, int s) {
        if (s > n) return;
        if (y == n) {
            y = 0;
            x ++;
        }
        if (x == n) {
            if (s == n) {
                for (char[] c : g)
                    System.out.println(String.valueOf(c));
                System.out.println();
            }
            return;
        }
        g[x][y] = '.';
        // 不放皇后
        dfs(x, y + 1, s);
        // 放皇后
        if (!row[x] && !col[y] && !dg[x + y] && !udg[n - y + x]) {
            g[x][y] = 'Q';
            row[x] = col[y] = dg[x + y] = udg[n - y + x] = true;
            dfs(x, y + 1, s + 1);
            row[x] = col[y] = dg[x + y] = udg[n - y + x] = false;
            g[x][y] = '.';

        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        g = new char[n][n];
        dfs(0, 0, 0);
    }
}

BFS

所有边的权重都为1时,才可以用BFS求最短路

走迷宫

import java.util.*;

public class Main {
    public static int bfs(int[][] g, int n, int m) {
        int[][] d = new int[n][m];
        for (int i = 0; i < n; ++ i)
            Arrays.fill(d[i], 0);

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        int[] dx = new int[]{0, -1, 0, 1}, dy = new int[]{1, 0, -1, 0};
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int i = 0; i < 4; ++ i) {
                int x = p[0] + dx[i], y = p[1] + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == 0) {
                    d[x][y] = d[p[0]][p[1]] + 1;
                    q.offer(new int[]{x, y});
                }
            }
        }
        return d[n - 1][m - 1];
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] g = new int[n][m];
        for (int i = 0; i < n; ++ i)
            for (int j = 0 ; j < m ; ++ j)
                g[i][j] = sc.nextInt();

        System.out.println(bfs(g, n, m));
    }
}

八数码

import java.util.*;

public class Main{

    public static int bfs(String start) {
        String end = "12345678x";

        HashMap<String, Integer> dMap = new HashMap<String, Integer>() {{
            put(start , 0);
        }};
        int[] dx = new int[]{0, 0, -1, 1}, dy = new int[]{1, -1, 0, 0};
        Queue<String> q = new LinkedList<>();
        q.offer(start);

        while (!q.isEmpty()) {
            StringBuilder sb = new StringBuilder(q.poll());
            String str = sb.toString();
            int distance = dMap.get(str);
            if (end.equals(str)) return distance;

            int k = sb.indexOf("x");
            int x = k / 3, y = k % 3;
            for (int i = 0; i < 4; ++ i) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                    int idx = a * 3 + b;
                    swap(sb, idx, k);
                    str = sb.toString();
                    if (!dMap.containsKey(str)) {
                        dMap.put(str, distance + 1);
                        q.offer(str);
                    }
                    swap(sb, idx, k);
                }
            }
        }
        return -1;
    }

    public static void swap (StringBuilder sb, int i, int j) {
        char tmp = sb.charAt(i);
        sb.setCharAt(i, sb.charAt(j));
        sb.setCharAt(j, tmp);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; ++ i)
            sb.append(sc.next());

        System.out.println(bfs(sb.toString()));
    }
}

Try and fail, but don't fail to try.