1.BFS简介
我们可以将bfs当做一个成熟稳重的人，一个眼观六路耳听八方的人，他每次搜索都是一层层的搜索，从第一层扩散到最后一层，BFS可以用来解决最短路问题。
2.基本思想
从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。
3.Acwing 844. 走迷宫
3.1题目
https://www.acwing.com/problem/content/846/
3.2bfs 过程手动模拟：
从起点开始，往前走第一步，记录下所有第一步能走到的点，然后从所第一步能走到的点开始，往前走第二步，记录下所有第二步能走到的点，重复下去，直到走到终点。输出步数即可。
3.3Ac代码
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; public class Main{ static int n,m,N=110; static int [][]p=new int[N][N]; //存储原始地图 static boolean [][]state=new boolean[N][N]; //每个点是否走过 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 = 1; i <=n; i++) { s=br.readLine().split(" "); for (int j =1; j <=m; j++) { p[i][j]=Integer.parseInt(s[j-1]); } } bfs(); br.close(); } private static void bfs() { int x=1,y=1; Queue<Point> q=new ArrayDeque<>(); //创建队列存储走过的每一个点 q.add(new Point(x,y,0)); //首先把第一个点存进队列 int []dy={0,-1,0,1}; int []dx={-1,0,1,0}; while (!q.isEmpty()){ Point head=q.poll(); //取出队首元素 if(head.x==n &&head.y==m){ //如果走到出口 System.out.println(head.step); return; } for (int i = 0; i < 4; i++) { //往四个方向走 x= head.x+dx[i]; y= head.y+dy[i]; if(x>0 &&x<=n &&y>0 &&y<=m &&!state[x][y] &&p[x][y]==0){ //如果还没有走过并且可以走 state[x][y]=true; q.add(new Point(x,y, head.step+1)); } } } } static class Point{ int x,y,step; Point(){ } public Point(int x, int y, int step) { this.x = x; this.y = y; this.step = step; } } }
4.Acwing 845. 八数码
4.1题目
https://www.acwing.com/problem/content/847/
4.2解题思路及模拟
暴力穷举。穷举出所有给定序列通过交换能得到的新序列，在穷举过程中保存交换次数。
在穷举过程中，如果出现了结果序列，就输出交换次数。
否则不能得到结果序列，输出 -1。
起始状态： 为 1 2 3 x 4 6 7 5 8
交换一次：
x 与上方元素交换得到： x 2 3 1 4 6 7 5 8
x 与右方元素交换得到： 1 2 3 4 x 6 7 5 8
x 与下方元素交换得到： 1 2 3 7 4 6 x 5 8
交换两次得到：
2 x 3 1 4 6 7 5 8
1 x 3 4 2 6 7 5 8
1 2 3 4 6 x 7 5 8
1 2 3 4 5 6 7 x 8
1 2 3 7 4 6 5 x 8
交换三次得到：
2 3 x 1 4 6 7 5 8
.....
1 2 3 4 5 6 7 8 x
.....
得到了最终结果，输出 3.
4.3Ac代码
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String []s=br.readLine().split(" "); String start=""; for (int i = 0; i < s.length; i++) { start+=s[i]; } System.out.println(bfs(start)); br.close(); } private static Integer bfs(String start) { String end="12345678x"; Queue<String> q=new ArrayDeque<>(); //存储所有状态 Map<String,Integer> state=new HashMap<>(); //存储每个状态得交换次数 q.add(start); state.put(start,0); //存初始状态 int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0};//四个方向 while (!q.isEmpty()){//枚举所有状态 String head=q.poll();//取出头一个状态并向前寻找（head过程中不能修改，因为有四次变化 而位置都是map[t]+1） if(head.equals(end)) return state.get(head); int k=head.indexOf('x'); //找到x所在的下标 int x=k/3,y=k%3; for (int i = 0; i < 4; i++) { int a=x+dx[i],b=y+dy[i];//变化状态之后x的下标 if(a>=0 &&a<3 &&b>=0 &&b<3){ //变换后不出界的就是可用的 char []ch=head.toCharArray();//字符串里面不能交换所以就到字符数组里 swap(ch,k,a*3+b); String s=new String(ch); if(state.get(s)==null){//如果这个状态没出现过就存储这个状态 q.add(s); state.put(s,state.get(head)+1); } } } } return -1; } private static void swap(char[] arr, int x, int y) { char c=arr[x]; arr[x]=arr[y]; arr[y]=c; } }
5.结尾
如果对java中队列的使用方法不熟悉的话可以看下java叶新东老师的这篇文章
