当前位置：网站首页>BFS题单总结
BFS题单总结
2022-07-30 22:45:00 【柯南二号】
BFS题单汇总
此文章用来记录遇到的经典的从某个点到达某个边界或者指定点的BFS题目，将持续更新
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;
}
}
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;
}
}
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
3
001
101
100
1 1 3 3
样例输出 #1
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要来寻找他的男家丁，大家一起来帮忙啊！
由于男家丁数目不多，再加上mzc大大的找人【laopo】水平很好，所以一次只需要找一个男家丁。
输入格式
第一行有两个数ｎ，m，表示有n行m列供男家丁躲藏，
之后n行m列的矩阵，‘m‘表示mzc，‘d’表示男家丁，‘#’表示不能走，‘.‘表示空地。
输出格式
一行，若有解：一个数ｓｕｍ，表示找到男家丁的最短移动次数。
若无解：输出“No Way!”。
样例 #1
样例输入 #1
5 6
.#..#.
....#.
d.....
#####.
m.....
样例输出 #1
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();
}
}
边栏推荐
- 通过社交媒体建立个人IP的 5 种行之有效的策略
- [MySQL] Mysql transaction and authority management
- Navicat new database
- 一文详解：SRv6 Policy模型、算路及引流
- 【CTF】buuctf web 详解（持续更新）
- Ningbo Zhongning Pawn will transfer 29.5% of the equity for 2.8338 million yuan, and the owner's equity in 2021 will be 9.6875 million yuan
- MySql统计函数COUNT详解
- IDEA使用技巧
- 3 minutes to take you to understand WeChat applet development
- cmd (command line) to operate or connect to the mysql database, and to create databases and tables
猜你喜欢
![[MySQL] DQL related operations](/img/a5/c92e0404c6a970a62595bc7a3b68cd.gif)
[MySQL] DQL related operations
cookie和session区别
Ningbo Zhongning Pawn will transfer 29.5% of the equity for 2.8338 million yuan, and the owner's equity in 2021 will be 9.6875 million yuan
MySQL 8.0.29 解压版安装教程（亲测有效）
QT 在父类中添加子类的流程，object tree，
MySQL Soul 16 Questions, How Many Questions Can You Last?
Py's pdpbox: a detailed introduction to pdpbox, installation, and case application
MySql 5.7.38下载安装教程 ,并实现在Navicat操作MySql
Detailed explanation of the delete problem of ClickHouse delete data
Go语学习笔记 - gorm使用 - 表增删改查 Web框架Gin（八）
随机推荐
Gxlcms audio novel system/novel listening system source code
2022/07/30 学习笔记 （day20） 面试题积累
cmd(命令行)操作或连接mysql数据库，以及创建数据库与表
【MySQL】DQL相关操作
PhpMetrics usage
The most powerful and most commonly used SQL statements in history
Successfully resolved ModuleNotFoundError: No module named 'Image'
[MySQL] DQL related operations
网安学习-内网渗透3
Day 16 of HCIP
Chapter 8 Intermediate Shell Tools II
使用LVS和Keepalived搭建高可用负载均衡服务器集群
Learning about XML (1)
Solve the problem of centos8 MySQL password ERROR 1820 (HY000) You must reset your password using the ALTER USER
解决一个Mysql的utf8编码导致的问题
MySQL Soul 16 Questions, How Many Questions Can You Last?
A detailed explanation: SRv6 Policy model, calculation and drainage
TCP 连接 三次握手 四次挥手
IDEA使用技巧
Navicat cannot connect to mysql super detailed processing method