当前位置：网站首页>Summary of BFS questions
Summary of BFS questions
2022-07-30 22:55:00 【Conan II】
BFS题单汇总
This article is used to record the classic encounters from a point to a boundary or a specified pointBFS题目,将持续更新
class Solution {
// n,mRepresents the given two-dimensional array or doubleList<List<Integer>>The length and width of this
// x0,y0Represents the given starting point coordinates
// dirThe array represents the coordinate direction for searching up, down, left, and right
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<>();
// Add starting point coordinates and cost steps
q.offer(new int[]{
x0, y0, 0});
// The starting point has been traversed,Mark the starting point as unreachable
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)The coordinates are not the same coordinates,且(tx,ty)already at the border,那就直接返回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)can continue to traverse,That will be the current coordinates(dx,dy)添加到队列里,And mark the current coordinate has been traversed
if (dx >= 0 && dx < n && dy >= 0 && dy < m && maze[dx][dy] == '.') {
q.offer(new int[]{
dx, dy, step + 1});
maze[dx][dy] = '+';
}
}
}
// If the specified location cannot be reached,那就返回-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添加到队列,and mark current(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];
// Judging that the line can continue to be traversed and added to the queue,At the same time, the number of steps that can continue to be traversed is the position that can be traversed last time(tx,ty)the number of steps to add1
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》最终章.
题目描述
After the God of Love and Sorrow finished shopping,I plan to leave Zhongshan Road by car.Now the great god of love and sorrow is herex1,y1处,车站在x2,y2处.现在给出一个n×n（n<=1000）的地图,0indicate the road,1表示店铺（You cannot pass through the store）,The Great God of Love and Sorrow can only travel on the road vertically or horizontally.God of love and sorrow to save time,He requires the shortest distance to the destination（a[i][j]距离为1）.你能帮他解决吗？
输入格式
第1行：一个数 n
第2行~第n+1行：The entire map description（0indicate the road,1表示店铺,Note that there is no space between the two numbers）
第n+2行：四个数 x1,y1,x2,y2
输出格式
只有1行：The shortest distance to the destination
样例 #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();
}
}
边栏推荐
- 正则表达式语法及使用
- 关于XML的学习（一）
- 成功解决ModuleNotFoundError: No module named ‘Image‘
- Apache Doris系列之：安装与部署详细步骤
- @RequestBody、 @RequestParam 、 @PathVariable 和 @Vaild 注解
- ＃yyds干货盘点＃ 面试必刷TOP101：判断链表中是否有环
- 2022.7.27
- mysql获取当前时间
- “由于找不到MSVCP140.dll,无法继续执行代码，重新安装程序可能会解决此问题等”解决方案
- When Navicat connects to MySQL, it pops up: 1045: Access denied for user 'root'@'localhost'
猜你喜欢
随机推荐
The problem of sticky packets in tcp protocol transmission
Installation and use of cnpm
2021GDCPC广东省大学生程序设计竞赛 H.History
matlab标量场作图
IJCAI2022教程 | 口语语言理解:最新进展和新领域
通过社交媒体建立个人IP的 5 种行之有效的策略
mysql锁机制
for...in 和 for...of 的区别
“蔚来杯“2022牛客暑期多校训练营4 L.Black Hole 垃圾计算几何
"NIO Cup" 2022 Nioke Summer Multi-School Training Camp 4 DHKLN
d违反常了吗
cmd (command line) to operate or connect to the mysql database, and to create databases and tables
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
第十九周进度（了解物联网基础知识）
PhpMetrics 使用
Go的Gin框架学习
EasyExcel综合课程实战
Excel基础学习笔记
d使用among的问题
微软商店出现【0x800706D9】解决方法