原创
上次用DFS解了迷宫救人：https://www.cnblogs.com/chiweiming/p/9313164.html
这次用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