蓝桥杯 Day12 java组 BFS

连通性判断

连通性判断是图论中的一个简单问题，就是找一张图中互相连通的部分，是基础的搜索，用 DFS 或 BFS 都行：

BFS判断连通性步骤：

从图上任意一个点 u 开始遍历，把它放进队列中。弹出队首 u，标记 u 已经搜过，然后搜索 u 的邻居点，若邻居点符合连通条件，放到队列中。继续弹出队首，标记搜过，然后搜索它的邻居，把符合连通条件的放进队列。继续以上步骤，直到队列为空。此时所有连通点都已经找到。DFS判断连通性步骤是：

从图上任意一个点 u 开始遍历，标记 u 已经搜过。递归 u 的所有符合连通条件的邻居点。递归结束，找到所有连通点。

无论 DFS 还是 BFS，连通性判断的计算复杂度是 O(n) 的，因为图上的所有点，最多进出队列一次。

第一题全球变暖

样例输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......

样例输出

import java.util.Scanner;

public class Main {
    private static int a;
    private static int flag;
    private static String strings[];
    private static char map[][];
    private static int visited[][];
    private static int count = 0;
    private static int dir[][] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        a = scanner.nextInt();
        strings = new String[a];
        map = new char[a][a];
        visited = new int[a][a];


        for (int i = 0; i < a; i++) {
            strings[i] = scanner.next();
        }

        for (int i = 0; i < a; i++) {
            for (int j = 0; j < a; j++) {
                map[i][j] = strings[i].charAt(j);
                visited[i][j] = 0;
            }
        }

        for (int i = 0; i < a; i++) {
            for (int j = 0; j < a; j++) {
                if (visited[i][j] == 0 && map[i][j] == '#') {
                    flag = 0;
                    dfs(i, j);
                    if (flag == 0) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }

    public static void dfs(int i, int j) {
        visited[i][j] = 1;
        if (map[i - 1][j] == '#' && map[i][j - 1] == '#' && map[i][j + 1] == '#' && map[i - +1][j] == '#') {
            flag = 1;
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dir[k][0];
            int y = j + dir[k][1];
            if (visited[x][y] != 1 && map[x][y] == '#') {
                dfs(x,y);
            }
        }
    }
}

import java.util.linkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static int a;
    private static int flag;
    private static String strings[];
    private static char map[][];
    private static int visited[][];
    private static int count = 0;
    private static int dir[][] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        a = scanner.nextInt();
        strings = new String[a];
        map = new char[a][a];
        visited = new int[a][a];


        for (int i = 0; i < a; i++) {
            strings[i] = scanner.next();
        }

        for (int i = 0; i < a; i++) {
            for (int j = 0; j < a; j++) {
                map[i][j] = strings[i].charAt(j);
                visited[i][j] = 0;
            }
        }

        for (int i = 0; i < a; i++) {
            for (int j = 0; j < a; j++) {
                if (visited[i][j] == 0 && map[i][j] == '#') {
                    flag = 0;
                    bfs(i, j);
                    if (flag == 0) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }

    public static void bfs(int i, int j) {
        Queue que = new linkedList();
        que.add(new Node(i, j));

        visited[i][j] = 1;
        while (!que.isEmpty()) {
            Node node = que.remove();
            int nx = node.x;
            int ny = node.y;
            if (map[nx - 1][ny] == '#' && map[nx][ny - 1] == '#' && map[nx][ny + 1] == '#' && map[nx - +1][ny] == '#') {
                flag = 1;
            }
            for (int k = 0; k < 4; k++) {
                int x = nx + dir[k][0];
                int y = ny + dir[k][1];
                if (visited[x][y] == 0 && map[x][y] == '#') {
                    visited[x][y] = 1;
                    que.add(new Node(x, y));
                }
            }
        }
    }
}

class Node {
    int x;
    int y;

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

第二题跳蚱蜢

化圈为线

import java.util.HashSet;
import java.util.linkedList;
import java.util.Queue;
import java.util.Set;

public class Main {
    private static String string = "087654321";
    private static int dir[] = new int[]{-2, -1, 1, 2};

    public static void main(String[] args) {
        bfs();
    }

    public static void bfs() {
        Queue queue = new linkedList();
        Set set = new HashSet();
        queue.add("012345678");
        set.add("012345678");
        int count = 0;
        while (!queue.isEmpty()) {
            int k = queue.size();
            for (int i = 0; i < k; i++) {
                String s = queue.poll();
                if (s.equals(string)) {
                    System.out.println(count);
                    return;
                }
                char[] chars = s.toCharArray();
                int temp = 0;
                for (int j = 0; j < chars.length; j++) {
                    if (chars[j] == '0') {
                        temp = j;
                        break;
                    }
                }
                for (int j = 0; j < dir.length; j++) {
                    char[] chars1 = chars.clone();
                    int temp2 = (temp + dir[j] + 9) % 9;
                    char c = chars[temp2];
                    chars1[temp2] = '0';
                    chars1[temp] = c;
                    String s2 = new String(chars1);
                    if (!set.contains(s2)) {
                        set.add(s2);
                        queue.add(s2);
                    }
                }
            }
            count++;
        }
    }
}

最短路径是 BFS 的经典应用。BFS 确实是一种很好的最短路径算法，不过，它只适合一种情况：任意的相邻两点之间距离相等。一般把这个距离看成1。这种情况下查找一个起点到一个终点的最短距离，BFS 是最优的最短路径算法，

而在求最短路径时，往往会伴随着两个问题：

最短路径有多长。答案是唯一的。最短路径经过了哪些点。由于最短路径可能不只一条，所以题目往往不要求输出，如果要求输出，一般是要求输出字典序最小的那条。

计算复杂度是 O(n)，n 是图上点的数量。

第三题迷宫

输入

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

import java.util.linkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    private static String[] strings = new String[50];
    private static char[][] chars = new char[100][100];
    private static int[][] direction = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    private static int[][] visited = new int[100][100];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < 30; i++) {
            strings[i] = scanner.next();
        }
        for (int i = 0; i < 30; i++) {
            for (int j = 0; j < 50; j++) {
                chars[i][j] = strings[i].charAt(j);
                visited[i][j] = 0;
            }
        }
        bfs();
    }

    private static void bfs() {
        Queue queue = new linkedList();
        queue.add(new Node(0, 0, null, 'D'));
        visited[0][0] = 1;
        Node node1 = null;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.x == 29 && node.y == 49) {
                node1 = node;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int x1 = node.x + direction[i][0];
                int y1 = node.y + direction[i][1];
                if (x1 >= 0 && x1 < 30 && y1 >= 0 && y1 < 50 && visited[x1][y1] == 0 && chars[x1][y1] == '0') {
                    char temp = ' ';
                    visited[x1][y1] = 1;
                    if (i == 0) temp = 'D';
                    if (i == 1) temp = 'L';
                    if (i == 2) temp = 'R';
                    if (i == 3) temp = 'U';
                    queue.add(new Node(x1, y1, node, temp));
                }
            }
        }
        Stack stack = new Stack<>();
        while (node1.pre != null) {
            stack.add(node1.ch);
            node1 = node1.pre;
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }
}

class Node {
    int x;
    int y;
    Node pre;
    char ch;

    public Node(int x, int y, Node pre, char ch) {
        this.x = x;
        this.y = y;
        this.pre = pre;
        this.ch = ch;
    }
}

答案：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

蓝桥杯 Day12 java组 BFS

Java相关栏目本月热门文章