Original

Last time, we used DFS to solve the maze and save people: https://www.cnblogs.com/chiweiming/p/9313164.html

This time, using BFS (breadth first search) to realize breadth first search is more complex than depth first search, and the idea is also more complex, but it is not difficult to understand.

Depth first search is a stroke down, a road to black;

Breadth first search is a multi-step search;

Both traverse all paths before finding the destination, but when finding the shortest path, use breadth first search once reaching the destination, namely

To generate the shortest path, depth first search needs to compare all the paths that can reach the destination.

The implementation of breadth first search uses queue to store the searched points, and then searches again based on these searched points.

The process of breadth first search can be represented by the following figure (traversing in the order of right, bottom, left and top):

The starting point is 1 (in the queue), and the points that can be reached within one step are 2 (in the queue) and 3 (in the queue), so search 2 and 3;

At this time, 1 is useless, 2 can go to 4 (team entry) and 5 (team entry), 2 is useless;

3 direct points are 5 (traversed) and 6 (in the team), 3 useless out of the team;

Each traversal point determines whether it is the hostage's point. If it is, the traversal stops.

Java:

import java.util.*; public class Labyrinth saves lives { 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 To show that the hostages int head=0; //Point to parent int tail=0; //Point to tail int maze[][]=new int[n][m]; //Maze int book[][]=new int[n][m]; //sign int x[]=new int[n*m]; //Queue abscissa int y[]=new int[n*m]; //Queue ordinate int step[]=new int[n*m]; //Queue steps int dir[][]= { {0,1},{1,0},{0,-1},{-1,0} //Right, down, left, up }; 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; //Starting node //Start node in queue x[tail]=0; y[tail]=0; step[tail]=0; tail++; //Tail pointer backward 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) { //Transboundary judgment continue; } if(maze[dx][dy]==1 || book[dx][dy]==1) { //Obstacles and access judgment continue; } //Eligible, queued book[dx][dy]=1; x[tail]=dx; y[tail]=dy; step[tail]=step[head]+1; tail++; if(maze[dx][dy]==2) { flag=1; //Finding hostages break; } } if(flag==1) { break; } head++; //Parent node out of team } System.out.println("("+x[tail-1]+","+y[tail-1]+")"+" "+step[tail-1]); } }

18:01:03

2018-07-19