此文章用来记录遇到的经典的从某个点到达某个边界或者指定点的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的步数
样例
样例输入
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要来寻找他的男家丁，大家一起来帮忙啊！
由于男家丁数目不多，再加上mzc大大的找人【laopo】水平很好，所以一次只需要找一个男家丁。
输入格式
第一行有两个数ｎ，m，表示有n行m列供男家丁躲藏，
之后n行m列的矩阵，‘m‘表示mzc，‘d’表示男家丁，‘#’表示不能走，‘.‘表示空地。
输出格式
一行，若有解：一个数ｓｕｍ，表示找到男家丁的最短移动次数。
若无解：输出“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(); } }
