原创
上次用DFS解了迷宫救人:
这次用BFS(广度优先搜索),实现广度优先搜索比深度优先搜索复杂,思路也复杂一些,但是不难理解。
深度优先搜索是一笔画下来,一条道走到黑;
广度优先搜索是多步同时进行,全面展开搜索;
两者都是在找到目的地前遍历所有路径,但是在寻找最短路径时,使用广度优先搜索一旦到达目的地,即
产生最短路径,而深度优先搜索需要比较所有能到达目的地的路径。
实现广度优先搜索用到了队列来存储目前已经搜查过的点,然后再在这些已经被搜查过的点的基础上再次搜索。
实现广度优先搜索的过程可以用下图来表示(按右、下、左、上的顺序来遍历):
起始点是1(入队列),1步之内可到达的点有2(入队列)和3(入队列),所以搜索2和3;
此时1已经无用,出队,2可以直达的点有4(入队)和5(入队),2无用出队;
3可直达的点有5(已遍历)和6(入队),3无用出队;
每遍历一个点判断是否为人质所在点,是则停止遍历。
Java:
import java.util.*; public class 迷宫救人 { static int n; static int m; public static void main(String[] args) { Scanner reader=new Scanner(System.in); n=reader.nextInt(); m=reader.nextInt(); int flag=0; //0表示人质为找到 int head=0; //指向父结点 int tail=0; //指向尾结点 int maze[][]=new int[n][m]; //迷宫 int book[][]=new int[n][m]; //标志 int x[]=new int[n*m]; //队列横坐标 int y[]=new int[n*m]; //队列纵坐标 int step[]=new int[n*m]; //队列步数 int dir[][]= { {0,1},{1,0},{0,-1},{-1,0} //右,下,左,上 }; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { maze[i][j]=reader.nextInt(); book[i][j]=0; } } book[0][0]=1; //起始结点 //起始结点入队列 x[tail]=0; y[tail]=0; step[tail]=0; tail++; //尾指针后移 while(head<=tail) { for(int i=0;i<4;i++) { int dx=x[head]+dir[i][0]; int dy=y[head]+dir[i][1]; if(dx<0 || dx>n-1 || dy<0 || dy>m-1) { //越界判断 continue; } if(maze[dx][dy]==1 || book[dx][dy]==1) { //障碍点和访问与否判断 continue; } //符合条件,入队列 book[dx][dy]=1; x[tail]=dx; y[tail]=dy; step[tail]=step[head]+1; tail++; if(maze[dx][dy]==2) { flag=1; //发现人质 break; } } if(flag==1) { break; } head++; //父结点出队 } System.out.println("("+x[tail-1]+","+y[tail-1]+")"+" "+step[tail-1]); } }
18:01:03
2018-07-19
如对本文有疑问, 点击进行留言回复!!
SpringBoot引用阿里easyexcel,Excel导出返回浏览器下载
HashMap、Hashtable、ConcurrentHashMap三者间的异同
解决RecycleView 中Item包含Edittext时,滑动view复用导致数据错乱的问题
多线程、同步工作原理、死锁案例、Lock接口、线程的生命周期的讲解及实现
网友评论