本文主要是介绍BFS中的Flood Fill和最短路模型，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
BFS：1、“求最小” 用bfs第一次搜到的值就是最小值
2、基迭代，不会爆栈
845. 八数码 - AcWing题库
import java.util.*;public class Main{public static void swap(char[] arr, int a, int b){char temp = arr[a];arr[a] = arr[b];arr[b] = temp;}public static int bfs(String start, String end){Map<String, Integer> map = new HashMap<>();//用来存储到达每种状态要走的距离Queue<String> q = new LinkedList<>();q.offer(start);map.put(start, 0);int[] dx = {-1,0,1,0}, dy = {0,1,0,-1};//上下左右四个方向while(!q.isEmpty()){String t = q.poll();//取出队头元素int k = t.indexOf('x');//找到元素x在这个字符串里的位置int x = k / 3;//找到等同在二维数组里面的坐标int y = k % 3;if(t.equals(end)) return map.get(t);//如果这时候已经相同了，就提前结束for(int i = 0; i < 4; i ++){//进行上下左右四种方案int a = x + dx[i], b = y + dy[i];//之前那种位移量的方法if(a < 3 && a >= 0 && b < 3 && b >= 0){//如果没有超出边界char[] arr = t.toCharArray();swap(arr, k, a * 3 + b);//交换位置，二维转化成一维//将交换位置后的字符数组变成新的字符串String str = new String(arr);if(map.get(str) == null){//说明这种状态还没有走到过map.put(str, map.get(t) + 1);//交换数加1q.offer(str);//加入队列}}}}return -1;}public static void main(String[] args){Scanner sc = new Scanner(System.in);String start = "";for(int i = 1; i <= 9; i ++){String s = sc.next();start += s;}String end = "12345678x";System.out.print(bfs(start, end));}
}Flood Fill算法：
可以在线性的时间复杂度内，找到某个点所在的连通块。
1097. 池塘计数 - AcWing题库
import java.util.*;
import java.io.*;class PII{int x, y;public PII(int x, int y){//一个点的横纵坐标this.x = x;this.y = y;}
}public class Main{static int N = 1010, M = N * N;static int n, m;static PII[] q = new PII[M];static char[][] g = new char[N][N];static boolean[][] st = new boolean[N][N];public static void bfs(int x, int y){int hh = 0, tt = -1;q[++ tt] = new PII(x, y);//把这个点加入队列while(hh <= tt){PII t = q[hh ++];//取出队头int a = t.x;//横坐标int b = t.y;//纵坐标for(int i = a - 1; i <= a + 1; i ++){for(int j = b - 1; j <= b + 1; j ++){if(i == a && j == b) continue;if(i < 0 || j < 0 || i >= n || j >= m) continue;//如果就是这个点if(g[i][j] == '.' || st[i][j]) continue;//如果不是水或者是已经遍历过了q[++ tt] = new PII(i, j);//把这个点加入队列st[i][j] = true;//标记位遍历过}}}}public static void main(String[] args)throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] s = br.readLine().split(" ");n = Integer.parseInt(s[0]);m = Integer.parseInt(s[1]);for(int i = 0; i < n; i ++){String str = br.readLine();char[] arr = str.toCharArray();for(int j = 0; j < m; j ++){g[i][j] = arr[j];}}int cnt = 0;//记录遍历了多少个连通块for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){if(g[i][j] == 'W' && !st[i][j]){//如果是水，而且没有遍历过bfs(i, j);cnt ++;}}}System.out.print(cnt);}
}
1098. 城堡问题 - AcWing题库
import java.util.*;class PII{int x, y;public PII(int x, int y){this.x = x;this.y = y;}
}public class Main{static int N = 60, M = N * N;static int n, m;static int[][] g = new int[N][N];static PII[] q = new PII[M];static boolean[][] st = new boolean[N][N];public static int bfs(int x, int y){int hh = 0, tt = -1;//队头和队尾int[] dx = {0, -1, 0, 1}, dy = {-1, 0, 1, 0};//西北东南四个方向q[++ tt] = new PII(x, y);//加入队列st[x][y] = true;//标记为已经遍历过int res = 0;//面积while(hh <= tt){PII t = q[hh ++];//取出元素res ++;//取出一个就加上一个for(int i = 0; i < 4; i ++){int a = t.x + dx[i];//四个方向int b = t.y + dy[i];if(a < 0 || b < 0 || a >= n || b >= m) continue;//越界if(st[a][b]) continue;//如果已经遍历过if((g[t.x][t.y] >> i & 1) == 1) continue;//用二进制来表示墙q[++ tt] = new PII(a, b);//加入队列st[a][b] = true;//标记为已经遍历过}}return res;}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i = 0; i < n; i++){for(int j = 0; j < m; j ++){g[i][j] = sc.nextInt();}}int cnt = 0;//连通块的数量int area = 0;//面积for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){if(!st[i][j]){area = Math.max(area, bfs(i, j));cnt ++;}}}System.out.println(cnt);System.out.println(area);}
}
1106. 山峰和山谷 - AcWing题库
import java.util.*;class PII{int x, y;public PII(int x, int y){this.x = x;this.y = y;}
}public class Main{static int N = 1010, M = N * N;static int n;static int[][] g = new int[N][N];static boolean[][] st = new boolean[N][N];static PII[] q = new PII[M];static boolean has_higher, has_lower;public static void bfs(int x, int y){int hh = 0, tt = -1;q[++ tt] = new PII(x, y);st[x][y] = true;//标记为走过while(hh <= tt){PII t = q[hh ++];for(int i = t.x - 1; i <= t.x + 1; i ++){for(int j = t.y - 1; j <= t.y + 1; j ++){if(t.x == i && t.y == j) continue;if(i < 0 || j < 0 || i >= n || j >= n) continue;if(g[i][j] != g[t.x][t.y]){//如果高度不相等if(g[i][j] > g[t.x][t.y]) has_higher = true;else has_lower = true;}else if(!st[i][j]){//如果高度相等st[i][j] = true;//标记为走过q[++ tt] = new PII(i, j);//存入队列}}}}}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();for(int i = 0; i < n; i ++){for(int j = 0; j < n; j ++){g[i][j] = sc.nextInt();}}int peak = 0;int vally = 0;for(int i = 0; i < n; i ++){for(int j = 0; j < n; j ++){if(!st[i][j]){//如果没走过has_higher = false;has_lower = false;bfs(i, j);if(!has_lower) vally ++;//只要没有比他矮的，那么他就是山谷if(!has_higher) peak ++;//只要没有比他高的，那么就是山峰}}}System.out.print(peak + " " + vally);}
}最短路问题
844. 走迷宫 - AcWing题库 是迷宫问题的简单版（迷宫问题要存路径）
1076. 迷宫问题 - AcWing题库
import java.util.*;
import java.io.*;class PII{int x, y;public PII(int x, int y){this.x = x;this.y = y;}
}public class Main{static int N = 1010, M = N * N, n;static int[][] g = new int[N][N];static PII[] q = new PII[M];static PII[][] pre = new PII[N][N];public static void bfs(int x, int y){int hh = 0, tt = -1;int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};//四个方向q[++ tt] = new PII(x, y);pre[x][y] = new PII(0, 0);//终点是由哪个点遍历来的while(hh <= tt){PII t = q[hh ++];for(int i = 0; i < 4; i ++){int a = t.x + dx[i];int b = t.y + dy[i];if(a >= n || b >= n || a < 0 || b < 0) continue;//边界if(g[a][b] == 1) continue;//墙if(pre[a][b].x != -1) continue;//如果前一个点的横坐标不为-1，那么说明遍历过q[++ tt] = new PII(a, b);//加入队列pre[a][b] = t;//这个点是由上一点过来的标记一下}}}public static void main(String[] args)throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));n = Integer.parseInt(br.readLine());for(int i = 0; i < n; i ++){String[] str = br.readLine().split(" ");for(int j = 0; j < n; j ++){g[i][j] = Integer.parseInt(str[j]);pre[i][j] = new PII(-1, -1);//标记为没遍历过}}bfs(n - 1, n - 1);//倒着来遍历PII end = new PII(0, 0);//输出路径while(true){System.out.println(end.x + " " + end.y);if(end.x == n - 1 && end.y == n - 1) break;end = pre[end.x][end.y];}}
}
188. 武士风度的牛 - AcWing题库
import java.util.*;
import java.io.*;class PII{int x, y;public PII(int x, int y){this.x = x;this.y = y;}
}public class Main{static int N = 200, M = N * N;static int n, m;static char[][] g = new char[N][N];static PII[] q = new PII[M];static int[][] dist = new int[N][N];public static int bfs(int a, int b){int hh = 0, tt = -1;int[] dx = {-2, -2, -1, 1, 2, 2, 1, -1};//八个方向int[] dy = {-1, 1, 2, 2, 1, -1, -2, -2};q[++ tt] = new PII(a, b);//加入队列dist[a][b] = 0;while(hh <= tt){PII t = q[hh ++];for(int i = 0; i < 8; i ++){int x = t.x + dx[i];int y = t.y + dy[i];if(x >= n || y >= m || x < 0 || y < 0) continue;//边界if(dist[x][y] != -1) continue;//如果走过了if(g[x][y] == '*') continue;//障碍if(g[x][y] == 'H') return dist[t.x][t.y] + 1;//到达目标dist[x][y] = dist[t.x][t.y] + 1;//步数加1q[++ tt] = new PII(x, y);//加入队列}}return -1;}public static void main(String[] args)throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] s = br.readLine().split(" ");m = Integer.parseInt(s[0]);n = Integer.parseInt(s[1]);for(int i = 0; i < n; i ++){String str = br.readLine();char[] arr = str.toCharArray();for(int j = 0; j < m; j ++){g[i][j] = arr[j];dist[i][j] = -1;//标记为没有走过}}for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){if(g[i][j] == 'K'){System.out.print(bfs(i, j));}}}}
}
1100. 抓住那头牛 - AcWing题库
import java.util.*;public class Main{static int N = 200010, n, k;static int[] dist = new int[N];static int[] q = new int[N];public static int bfs(){int hh = 0, tt = -1;q[++ tt] = n;dist[n] = 0;Arrays.fill(dist, -1);//初始化表示没来过while(hh <= tt){int t = q[hh ++];if(t == k) return dist[k] + 1;//到达终点，结果加1if(t - 1 >= 0 && dist[t - 1] == -1){dist[t - 1] = dist[t] + 1;q[++ tt] = t - 1;}if(t + 1 < N && dist[t + 1] == -1){dist[t + 1] = dist[t] + 1;q[++ tt] = t + 1;}if(2 * t < N && dist[2 * t] == -1){dist[2 * t] = dist[t] + 1;q[++ tt] = 2 * t;}}return -1;}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();k = sc.nextInt();System.out.print(bfs());}
}
这篇关于BFS中的Flood Fill和最短路模型的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
