# Another maze to save people - BFS

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) {
int flag=0;    //0 To show that the hostages
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++) {
book[i][j]=0;
}
}
book=1;    //Starting node
//Start node in queue
x[tail]=0;
y[tail]=0;
step[tail]=0;
tail++;    //Tail pointer backward
for(int i=0;i<4;i++) {
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;
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

Keywords: Java

Added by TheHeretic on Sun, 09 Feb 2020 17:52:25 +0200