跟着y总学了之后防止忘记稍微总结一下首先搜索主要是两部分其一是深度优先搜索其二则是宽度优先搜索。其中宽度优先搜索更简单一下所以先说一下宽度优先搜索。宽度优先搜索BFS1.定义用自己的话来总结理解就是在遍历一个树的时候优先遍历自己的兄弟树直到兄弟树全部遍历完之后才会遍历自己的子树。2.常用结构宽搜常常和队列一起使用。3.适用的题型1.搜索连通块搜索图中的连通块的块数或者是搜索该点所在的连通块有哪些元素时我们可以使用宽搜。代码如下搜索连通块的块数我们以Flood Fill模型为例例题Acwing 池塘计数import java.util.*; public class Main{ static class Node{ int x , y; public Node(int x , int y){ this.x x; this.y y; } } static int cut 0; static boolean vt[][] new boolean[1100][1100]; static char[][] root new char[1100][1100]; static int d[][] {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; static int n , m; 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){ root[i] sc.next().toCharArray(); } for(int i 0 ; i n ; i){ for(int j 0 ; j m ; j){ if(root[i][j] W !vt[i][j]){ vt[i][j] true; bfs(new Node(i,j)); cut; } } } System.out.println(cut); } public static void bfs(Node o){ QueueNode qu new LinkedList(); qu.add(o); while(!qu.isEmpty()){ Node node qu.poll(); int x node.x; int y node.y; for(int i 0 ; i 8 ; i){ int a x d[i][0]; int b y d[i][1]; if(a 0 || a n || b 0 || b m) continue; if(root[a][b] .) continue; if(vt[a][b]) continue; vt[a][b] true; qu.add(new Node(a,b)); } } } }2.最短距离使用bfs寻求最短距离必须要满足的一个点就是每条边的权值必须相等只有这样的话 才能够使用bfs求最短距离。但是呢我们在计算最短距离的时候又有需要注意的点了那就是起点是否唯一如果唯一的话那就是我们常规的求最短距离了直接配合题意使其与模板相结合就行但是如果是起点不唯一的话那我们就要设置一个虚拟源点了将这个虚拟源点与所有的起点连接起来在做题的时候我们可以直接把所有的起点事先加入到队列当中然后再对队列进行处理。下面通过两个例题来说明这两种情况单源求最短路Acwing 红与黑import java.util.*; public class Main { static class Node{ int x,y; public Node(int x, int y) { this.x x; this.y y; } } static int R,C; static int N 210; //也可以将距离存在Node静态类中 static int [][]dist new int[N][N];//记录最短距离 static char[][] g new char[N][N];//原数组 // 定义偏移量 static int[] dx new int[]{-1,0,1,0}; static int[] dy new int[]{0,1,0,-1}; static Node start,end; public static void main(String[] args) { Scanner scanner new Scanner(System.in); int T scanner.nextInt(); while(T-- 0) { R scanner.nextInt(); C scanner.nextInt(); for (int j 0; j R; j) { String line scanner.next(); g[j] line.toCharArray(); for (int k 0; k C; k) { if (g[j][k] S) { start new Node(j, k); } else if (g[j][k] E) end new Node(j, k); } } // 现在为止已经拿到了迷宫开始解答 int res BFS(start, end); if (res -1) System.out.println(oop!); else System.out.println(res); } } static int BFS(Node start,Node end){ QueueNode queue new LinkedList(); for (int i 0; i R; i) { Arrays.fill(dist[i],-1); } dist[start.x][start.y] 0; queue.add(start); while(!queue.isEmpty()){ Node t queue.poll(); for (int i 0; i 4; i) { int x t.x dx[i]; int y t.y dy[i]; if (x 0 || x R || y 0 ||y C ) continue; if (g[x][y] #) continue; if (dist[x][y] ! -1) continue; dist[x][y] dist[t.x][t.y] 1; if (x end.x y end.y) return dist[x][y]; queue.add(new Node(x,y)); } } return -1; } }多源求最短路 Acwing 矩阵距离import java.util.*; public class Main{ static class Node{ int x , y , step; public Node(int x , int y , int step){ this.x x; this.y y; this.step step; } } static int N 1010; static int d[][] {{0,1},{0,-1},{1,0},{-1,0}}; static int[][] root new int[N][N]; static boolean[][] vt new boolean[N][N]; static QueueNode qu new LinkedList(); static int n , m; static int dist[][] new int[N][N]; 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){ char c[] sc.next().toCharArray(); Arrays.fill(dist[i],-1); for(int j 0 ; j m ; j){ root[i][j] c[j] - 0; if(root[i][j] 1){ qu.add(new Node(i,j,0)); vt[i][j] true; } } } bfs(); for(int i 0 ; i n ; i){ for(int j 0 ; j m ; j){ System.out.print(dist[i][j] ); } System.out.println(); } } static void bfs(){ while(!qu.isEmpty()){ Node o qu.poll(); int x o.x; int y o.y; int step o.step; dist[x][y] step; for(int i 0 ; i 4 ; i){ int nx x d[i][0]; int ny y d[i][1]; if(nx 0 || nx n || ny 0 || ny m) continue; if(vt[nx][ny]) continue; vt[nx][ny] true; qu.add(new Node(nx,ny,step 1)); } } } }3.求最小步数虽然这个类型的题好像和上一个一样但是他们其实是有不同之处的用一个例子来 说明的话就是上一类题对应得是餐厅里有两个相互认识得顾客他俩想搭话但是又里的太远了所以A决定去找B以方便他们聊天。但是对于这一类题他对应得是一个餐厅的座位保持不变里面的顾客自己换位置直到换到每个人都到了正确的位置问最少要几步 。对于数据量正常的题的话我们基本就是通过模板就可以完成但是对于数据量极大的题的话这时我们就要进行双向广搜来解决问题双向广搜就是起点和终点交替寻求一条找到对方的最短的路何为交替寻求就是谁队列中的元素更少谁就先搜下面来通过两个个例题来说明Acwing 八数码import java.util.*; public class Main{ static class Node{ String str ; int step 0; public Node(String str , int step){ this.str str; this.step step; } } static SetString set new HashSet(); static QueueNode qu new LinkedList(); static String end 12345678x; static int dx[] {1,0,-1,0}; static int dy[] {0,1,0,-1}; public static void main(String[] args){ Scanner sc new Scanner(System.in); String c[] sc.nextLine().split( ); String s ; for(int i 0 ; i c.length ; i) s sc[i]; qu.add(new Node(s,0)); set.add(s); bfs(); } public static void bfs(){ while(!qu.isEmpty()){ Node node qu.poll(); String s node.str; int step node.step; if(s.equals(end)){ System.out.println(step); return; } int k s.indexOf(x); int x k / 3; int y k % 3; for(int i 0 ; i 4 ; i ){ int nx x dx[i]; int ny y dy[i]; if(nx 0 || nx 2 || ny 0 || ny 2) continue; char c[] s.toCharArray(); int t nx * 3 ny; c[k] c[t]; c[t] x; String new_str String.valueOf(c); if(!set.contains(new_str)){ qu.add(new Node(new_str,step 1)); set.add(new_str); } } } System.out.println(-1); } }Acwing字串变化双向广搜import java.util.*; import java.io.*; public class Main{ static QueueString qa new LinkedList(); static QueueString qb new LinkedList(); static MapString,Integer ma new HashMap(); static MapString,Integer mb new HashMap(); static String da[] new String[6]; static String db[] new String[6]; static String A , B; static int n; public static void main(String[] args) throws IOException{ BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String s[] br.readLine().split( ); A s[0]; B s[1]; while(br.ready()){ s br.readLine().split( ); da[n] s[0]; db[n] s[1]; } int t bfs(); if(t 10) System.out.println(t); else System.out.println(NO ANSWER!); } public static int bfs(){ if(A.equals(B)) return 0; qa.add(A); qb.add(B); ma.put(A,0); mb.put(B,0); while(qa.size() 0 qb.size() 0){ int t 0;//每一次扩展 if(qa.size() qb.size()) t extend(qa,ma,mb,da,db); else t extend(qb,mb,ma,db,da); if(t 10) return t; } return 11; } public static int extend(QueueString qa , MapString,Integer ma , MapString,Integer mb , String[] da , String[] db){ String s qa.poll(); for(int i 0 ; i s.length() ; i){ for(int j 0 ; j n ; j){ int idx s.indexOf(da[j],i); if(idx -1) continue; String state s.substring(0,idx) db[j] s.substring(idx da[j].length()); if(mb.containsKey(state)) return ma.get(s) 1 mb.get(state); if(ma.containsKey(state)) continue; ma.put(state,ma.get(s) 1); qa.add(state); i idx; } } return 11; } }