BFS题单总结

2023-05-16

BFS题单汇总

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

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

class Solution {
	// n,m代表给定二维数组或者二重List<List<Integer>>这种的长和宽
	// 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;
    }
}

1970.你能穿过矩阵的最后一天

class Solution {
    public int latestDayToCross(int row, int col, int[][] cells) {
        int n = row;
        int m = col;
        int ans = 0;
        int l = 0;
        int r = n * m;
        int[][] dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        while (l <= r) {
            int mid = l + r >> 1;
            int[][] grid = new int[n][m];
            for (int i = 0; i < n; i++) {
                Arrays.fill(grid[i], 0);
            }
            for (int i = 0; i < mid; i++) {
                grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
            }
            Queue<int[]> q = new ArrayDeque<>();
            for (int j = 0; j < m; j++) {
                if (grid[0][j] == 0) {
                    q.offer(new int[]{0,j});
                    grid[0][j] = 1;
                }
            }
            boolean f = false;
            while (!q.isEmpty()) {
                int[] arr = q.poll();
                int tx = arr[0];
                int ty = arr[1];
                for (int k = 0 ; k < 4 ; k++) {
                    int dx = dir[k][0] + tx;
                    int dy = dir[k][1] + ty;
                    if (dx >= 0 && dx < n && dy >= 0 && dy < m && grid[dx][dy] == 0) {
                        if (dx == n - 1) {
                            f = true;
                            break;
                        }
                        q.offer(new int[]{dx, dy});
                        grid[dx][dy] = 1;
                    }
                }
            }
            if (f) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
            
        }
        return ans;
    }
}

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;
    }

}

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

8 
9

提示

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;
    }

}

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

样例输出 #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;
    }

}

P2298 Mzc和男家丁的游戏

题目背景

ｍｚｃ与ｄｊｎ的第二弹。

题目描述

ｍｚｃ家很有钱（开玩笑），他家有ｎ个男家丁（做过上一弹的都知道）。他把她们召集在了一起，他们决定玩捉迷藏。现在mzc要来寻找他的男家丁，大家一起来帮忙啊！

由于男家丁数目不多，再加上mzc大大的找人【laopo】水平很好，所以一次只需要找一个男家丁。

输入格式

第一行有两个数ｎ，m，表示有n行m列供男家丁躲藏，

之后n行m列的矩阵，‘m‘表示mzc，‘d’表示男家丁，‘#’表示不能走，‘.‘表示空地。

输出格式

一行，若有解：一个数ｓｕｍ，表示找到男家丁的最短移动次数。

若无解：输出“No Way!”。

样例 #1

样例输入 #1

5 6
.#..#.
....#.
d.....
#####.
m.....

样例输出 #1

提示

3=<M,n<=2000

由于mzc大大十分着急，所以他只能等待1S。

package luogu.bfs.p2298;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.PriorityQueue;

public class Main {

    static int N = 2010;
    static int n;
    static int m;
    // 设定起点(x0, y0)坐标
    static int x0;
    static int y0;
    static PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
    static int[][] dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    static boolean[][] vis = new boolean[N][N];
    static char[][] grid = new char[N][N];

    public static void main(String[] args) throws IOException {
        Read read = new Read();
        String[] s = read.getStringLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 0; i < n; i++) {
            String str = read.getStringLine();
            for (int j = 0; j < m; j++) {
                grid[i][j] = str.charAt(j);
                if ('m' == grid[i][j]) {
                    x0 = i;
                    y0 = j;
                }
            }
        }
        int x = bfs();
        String res = x == -1 ? "No Way!" : String.valueOf(x);
        System.out.println(res);
    }

    public static int bfs() {
        q.offer(new int[]{x0, y0, 0});
        vis[x0][y0] = true;
        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int tx = arr[0];
            int ty = arr[1];
            int step = arr[2];
            if (grid[tx][ty] == 'd') {
                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 < 0 || dx >= n || dy < 0 || dy >= m ){
                   continue;
                }
                if (grid[dx][dy] == '#' || vis[dx][dy]) {
                    continue;
                }
                vis[dx][dy] = true;
                q.offer(new int[]{dx, dy, step + 1});
            }
        }
        return -1;
    }

}

class Read {

    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    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;
    }

    public String getStringLine() throws IOException {
        return reader.readLine();
    }
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

BFS

题单总结