• BFS模板

    此文章用来记录遇到的经典的从某个点到达某个边界或者指定点的BFS题目，将持续更新

    1926. 迷宫中离入口最近的出口

    class Solution {
	// n,m代表给定二维数组或者二重List>这种的长和宽
	// x0,y0代表给定的起点坐标
	// dir数组代表的是进行上下左右搜索的坐标方向
    int n;
    int m;
    int x0;
    int y0;
    int[][] dir = {{1,0}, {-1, 0}, {0, -1}, {0,1}};
    public int nearestExit(char[][] maze, int[] entrance) {
        n = maze.length;
        m = maze[0].length;
        x0 = entrance[0];
        y0 = entrance[1];
        return bfs(maze, x0, y0);
    }

    public int bfs(char[][] maze, int i, int j) {
        Queue<int[]> q = new ArrayDeque<>();
        // 添加起始点坐标以及耗费步数
        q.offer(new int[]{x0, y0, 0});
        // 已经遍历过起始点，标记起始点为不可达
        maze[x0][y0] = '+';
        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int tx = arr[0];
            int ty = arr[1];
            int step = arr[2];
            // 如果(tx,ty)坐标与(i,j)坐标不是同一个坐标，且(tx,ty)已经在边界，那就直接返回step步数
            if ( !(tx == i && ty == j) && (tx == 0 || tx == n - 1|| ty == 0 || ty == m - 1) ) {
                return step;
            }
            // 进行方向遍历
            for (int k = 0 ; k < 4; k++) {
            // 上下左右方向，其中dx代表横坐标，dy代表纵坐标
                int dx = tx + dir[k][0];
                int dy = ty + dir[k][1];
                // 如果(dx,dy)在(0,0)~(n - 1, m - 1)范围内，且(dx,dy)是可以继续遍历的，那就将当前坐标(dx,dy)添加到队列里，并标记当前坐标已经遍历过了
                if (dx >= 0 && dx < n && dy >= 0 && dy < m && maze[dx][dy] == '.') {
                    q.offer(new int[]{dx, dy, step + 1});
                    maze[dx][dy] = '+';
                }
            }
        }
        // 如果无法到达指定位置，那就返回-1
        return -1;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    P1443 马的遍历

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {


    static int n;
    static int m;
    static int x0;
    static int y0;
    static Queue<int[]> q = new ArrayDeque<>();
    static int[][] f;
    static int[][] dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    static int[][] directions = {{-1, 2},{-2, 1},{-2, -1}, {-1, -2}, {1, 2},{2, 1}, {2, -1}, {1,-2} };
    static boolean[][] vis;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        x0 = Integer.parseInt(s[2]);
        y0 = Integer.parseInt(s[3]);
        vis = new boolean[n + 10][m + 10];
        f = new int[n + 10][m + 10];
        for (int[] x : f) {
            Arrays.fill(x, -1);
        }
        // x0, y0添加到队列，且标记当前(x0,y0)已经遍历过了
        q.offer(new int[]{x0, y0});
        f[x0][y0] = 0;
        vis[x0][y0] = true;
        bfs(x0, y0);
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1; j <= m ; j++) {
                System.out.printf("%-5d",f[i][j]);
            }
            if (i != n) {
                System.out.println();
            }
        }
    }

    public static void bfs(int i,int j) {
        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int tx = arr[0];
            int ty = arr[1];
            for (int k = 0; k < directions.length; k++) {
                int dx = tx + directions[k][0];
                int dy = ty + directions[k][1];
                // 判断符合可以继续遍历到的添加到队列，同时可以继续遍历到的步数为上次可以遍历到的位置(tx,ty)的步数加1
                if (dx >= 1 && dx <= n && dy >=1 && dy <= m && !vis[dx][dy]) {
                    q.offer(new int[]{dx, dy});
                    vis[dx][dy] = true;
                    f[dx][dy] = f[tx][ty] + 1;
                }
            }
        }
    }

}

class Read {

    StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));

    public int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    public double nextDouble() throws IOException {
        st.nextToken();
        return st.nval;
    }

    public String nextString() throws IOException {
        st.nextToken();
        return st.sval;
    }

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    P1747 好奇怪的游戏

    题目背景

    《爱与愁的故事第三弹·shopping》娱乐章。

    调调口味来道水题。

    题目描述

    爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？

    输入格式

    第1行：两个整数x1，y1

    第2行：两个整数x2，y2

    输出格式

    第1行：黑马到1,1的步数

    第2行：白马到1,1的步数

    样例 #1

    样例输入 #1

    12 16
18 10

    • 1
    • 2

    样例输出 #1

    8 
9

    • 1
    • 2

    提示

    100%数据：x1,y1,x2,y2<=20

    

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {


    static int x0;
    static int y0;
    static int x1;
    static int y1;
    static int[][] dir = {{1, -2}, {1, 2}, {-1, -2}, {-1, 2}, {2, -1}, {2, 1}, {-2, -1}, {-2, 1},{2,2}, {2,-2},{-2,2},{-2,-2}};
    static int N = 60;
    static boolean[][] vis = new boolean[N][N];
    static Queue<int[]> q = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        Read read = new Read();
        x0 = read.nextInt();
        y0 = read.nextInt();
        x1 = read.nextInt();
        y1 = read.nextInt();
        System.out.println(bfs(1,1, x0, y0));
        while (!q.isEmpty()) {
            q.poll();
        }
        for (boolean[] v : vis) {
            Arrays.fill(v, false);
        }
        System.out.println(bfs(1,1, x1, y1));
    }

    public static int bfs(int i, int j, int x, int y) {
        q.offer(new int[]{i, j, 0});
        vis[i][j] = true;
        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int tx = arr[0];
            int ty = arr[1];
            int step = arr[2];
            for (int k = 0; k < dir.length; k++) {
                int dx = tx + dir[k][0];
                int dy = ty + dir[k][1];
                if (dx >= 1 && dx <= 50 && dy >= 1 && dy <= 50 && !vis[dx][dy]) {
                    q.offer(new int[]{dx, dy, step + 1});
                    vis[dx][dy] = true;
                }
                if (tx == x && ty == y) {
                    return step;
                }
            }
        }
        return -1;
    }

}

class Read {

    StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));

    public int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    public double nextDouble() throws IOException {
        st.nextToken();
        return st.nval;
    }

    public String nextString() throws IOException {
        st.nextToken();
        return st.sval;
    }

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83

    P1746 离开中山路

    题目背景

    《爱与愁的故事第三弹·shopping》最终章。

    题目描述

    爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在x1,y1处，车站在x2,y2处。现在给出一个n×n（n<=1000）的地图，0表示马路，1表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1）。你能帮他解决吗？

    输入格式

    第1行：一个数 n

    第2行~第n+1行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格）

    第n+2行：四个数 x1,y1,x2,y2

    输出格式

    只有1行：最短到达目的地距离

    样例 #1

    样例输入 #1

    3
001
101
100
1 1 3 3

    • 1
    • 2
    • 3
    • 4
    • 5

    样例输出 #1

    4

    • 1

    提示

    20%数据：n<=100

    100%数据：n<=1000

    

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {


    static int n;
    static int N = 1010;
    static int[][] arr = new int[N][N];
    static boolean[][] vis = new boolean[N][N];
    static int[][] dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    static Queue<int[]> q = new ArrayDeque<>();
    static int x0;
    static int y0;
    static int x;
    static int y;

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(read.readLine());
        for (int i = 1; i <= n; i++) {
            String s = read.readLine();
            for (int j = 1; j <= n; j++) {
                arr[i][j] = s.charAt(j - 1) - '0';
            }
        }
        String[] num = read.readLine().split(" ");
        x0 = Integer.parseInt(num[0]);
        y0 = Integer.parseInt(num[1]);
        x = Integer.parseInt(num[2]);
        y = Integer.parseInt(num[3]);
        q.offer(new int[]{x0, y0, 0});
        int res = dfs();
        System.out.println(res);
    }

    public static int dfs() {
       while (!q.isEmpty()) {
           int[] a = q.poll();
           int tx = a[0];
           int ty = a[1];
           int step = a[2];
           if (arr[tx][ty] == 1) {
               continue;
           }
           if (tx == x && ty == y) {
               return step;
           }
           vis[tx][ty] = true;
           for (int k = 0; k < 4; k++) {
               int dx = tx + dir[k][0];
               int dy = ty + dir[k][1];
               if (dx >= 1 && dx <= n && dy >= 0 && dy <= n && !vis[dx][dy] && arr[dx][dy] == 0) {
                   q.offer(new int[]{dx, dy, step + 1});
                   vis[dx][dy] = true;
               }
           }
       }
        return -1;
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
  • 相关阅读:
    生活无趣感的成因与破解之道
    【面试题】- Docker
    27、商户查询缓存（添加商户缓存）
    upload-labs关卡9(基于win特性data流绕过)通关思路
    原生GO开发的博客系统
    2.10.2版本的青龙升级2.10.13及2.11.3版本的教程
    【Linux】常用系统工作命令
    Java环境变量学习
    [深度学习][预训练模型]darknet-yolov7预训练模型下载地址
    远距离串口服务器（ 适配器）UART 转 1-Wire 应用
  • 原文地址：https://blog.csdn.net/qq_41688840/article/details/126004325