BFS题单总结

简介: 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的步数

样例

样例输入

12 16
18 10

样例输出

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行:最短到达目的地距离

样例

样例输入

3
001
101
100
1 1 3 3

样例输出

4

提示

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与djn的第二弹。

题目描述

mzc家很有钱(开玩笑),他家有n个男家丁(做过上一弹的都知道)。他把她们召集在了一起,他们决定玩捉迷藏。现在mzc要来寻找他的男家丁,大家一起来帮忙啊!

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

输入格式

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

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

输出格式

一行,若有解:一个数sum,表示找到男家丁的最短移动次数。

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

样例

样例输入

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

样例输出

12

提示

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


相关文章
|
3月前
|
存储 算法
BFS算法的实现
BFS算法的实现
48 1
|
6月前
|
存储 人工智能
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(中)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
47 0
|
6月前
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(下)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
36 0
|
6月前
|
算法
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(上)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
92 0
|
6月前
|
存储 算法
使用 BFS 解决走迷宫问题
使用 BFS 解决走迷宫问题
74 1
|
6月前
|
存储 算法 定位技术
图论算法dijkstra dfs bfs以及动态规划
图论算法dijkstra dfs bfs以及动态规划
82 0
|
存储 前端开发 算法
深度优先搜索(DFS)和广度优先搜索(BFS)
深度优先搜索(DFS)和广度优先搜索(BFS)
121 0
|
算法 C++
BFS从0到1
BFS从0到1
97 0
|
算法 定位技术
算法 | 广度优先遍历BFS
算法 | 广度优先遍历BFS
97 0