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