下面介绍BFS求迷宫题的解法。
在迷宫题中，BFS一般用于求迷宫中起点到终点的最短路径sp（DFS一般用于求迷宫中起点到终点的路径总条数）
下面以经典例题为例，给大家BFS算法求解迷宫题的模板，习题1中BFS算法中附有详细注释，后面的习题中没有
习题1：BFS_走字符迷宫
给你一个n行m列的二维迷宫。‘S’表示起点，‘T’ 表示终点，’#’ 表示墙壁，’.’ 表示平地。
你需要从 ‘S’ 出发走到 ‘T’，每次只能上下左右走动，
并且不能走出地图的范围以及不能走到墙壁上。请你计算出走到终点需要走的最少步数。
输入格式
第一行输入n, m表示迷宫大小。【1≤n,m≤100】
接下来输入n行字符串表示迷宫，每个字符串长度为m。
（地图保证有且仅有一个终点，一个起始点）
输出格式
【输出走到终点的最少步数，如果不能走到终点输出−1，占一行。】
/*
样例1：
输入
3 3
S.#
.#.
.#T
输出
-1
样例2：
输入
5 5
S.###
#....
#.#.#
#.#.#
#.#.T
输出
8
样例3：
输入
6 6
...S..
.#.##.
......
...##.
.#.#..
.T....
输出
7
*/
import java.util.*;
public class BFS_走字符迷宫{
//要用Queue的时候，如果是用<Integer>,那每个点只能存一个数字
//由于坐标至少要有x、y两个数字，所以必须建新类node,然后Queue<node>
static class node{
int x;
int y;
int step; //step用于存放起点到当前坐标的最少步数（即层数）
//在这里还可以存其他某些内容
node(int x,int y,int step){
this.x=x;
this.y=y;
this.step=step;
}
}
static int MAXV=999;
static int n,m; //大小为n*m的地图
static int[][] map2=new int[MAXV][MAXV]; //二选一,输入全为数字的地图
static char[][] map=new char[MAXV][MAXV]; //二选一,输入含有字符的地图
static boolean[][] inq=new boolean[MAXV][MAXV]; //判定该点是否进过队
static int sp=-1; //最终结果shortest path，用于存最短路径的长度。如果无路径，返回-1
//move数组的元素顺序，会决定遍历时的顺序，本例中顺序为“上下左右”
static int[][] move= {{-1,0},{1,0},{0,-1},{0,1}};
//bfs算法
public static void bfs(int x,int y) {
//如果有需要，也可以把queue放到方法外面，加上static，作为类变量
Queue<node> q=new LinkedList<node>();
q.add(new node(x,y,0));
inq[x][y]=true;
while(!q.isEmpty()) {
//1、进来之后，要做什么
node temp=q.poll();
// inq[temp.x][temp.y]=true; //错误，inq数组的含义为结点是否已入过队，而非结点是否已被访问
//2、如果是终点，要做什么
if(map[temp.x][temp.y]=='T') {
sp=temp.step;
return ;
}
//3、如果不是终点，要做什么
for(int i=0;i<4;i++) { //循环4次，得到4个相邻位置
//不能直接改变原结点中的x,y,path的值，要另设变量
int nx=temp.x+move[i][0];
int ny=temp.y+move[i][1];
int nstep=temp.step+1;
if(check(nx,ny)) {
q.offer(new node(nx,ny,nstep));
inq[nx][ny]=true; //注意，结点入队时，要立即标记已入队
}
}
}
}
//边界条件和约束条件的判断,约束条件由实际题目决定
public static boolean check(int x,int y) {
//注意是map[x][y]!='#',如果改成map[x][y]=='.',会忽略‘T’的情况
if(x>=0&&y>=0&&x<n&&y<m&&!inq[x][y]&&map[x][y]!='#')
return true;
else return false;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
//不能在n,m之前写int
n=sc.nextInt();
m=sc.nextInt();
int x=0,y=0;
for(int i=0;i<n;i++) {
String s=sc.next();
for(int j=0;j<s.length();j++) {
if(s.charAt(j)=='S') {
x=i;
y=j;
}
}
map[i]=s.toCharArray();
}
bfs(x,y);
// 如果跑完dfs后还需要进行其他某些操作，就在这里写
System.out.println(sp);
sc.close();
}
}
得到了BFS的模板之后，再来练习一下下面这道字符迷宫的例题
习题2：BFS_走字符迷宫2
描述
一个迷宫由n行m列格子组成，#格子里有障碍物，不能走；. 格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。
只能在水平方向或垂直方向走，不能斜着走。
/*
样例输入
5 5
..###
#....
#.#.#
#.#.#
#.#..
样例输出
9
*/
import java.util.*;
public class 走字符迷宫2bfs {
static class node{
int x;
int y;
int path;
node(int x,int y,int path){
this.x=x;
this.y=y;
this.path=path;
}
}
static int MAXV=999;
static int n,m;
static int sp=-1;
static char[][] map=new char[MAXV][MAXV];
static int[][] v=new int[MAXV][MAXV];
static int[][] move= {{0,1},{0,-1},{1,0},{-1,0}};
public static void bfs(int x,int y) {
Queue<node> q=new LinkedList<node>();
q.offer(new node(x,y,1));
while(!q.isEmpty()) {
node temp=q.poll();
v[temp.x][temp.y]=1;
if(temp.x==n-1&&temp.y==m-1) {
sp=temp.path;
return ;
}
for(int i=0;i<4;i++) {
int nx=temp.x+move[i][0];
int ny=temp.y+move[i][1];
int npath=temp.path+1;
if(check(nx,ny)) {
q.offer(new node(nx,ny,npath));
}
}
}
}
public static boolean check(int x,int y) {
if(x>=0&&y>=0&&x<n&&y<m&&map[x][y]=='.')
return true;
else return false;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(int i=0;i<n;i++) {
String s=sc.next();
map[i]=s.toCharArray();
}
bfs(0,0);
System.out.println(sp);
}
}
熟练掌握了BFS模板并且会做简单题之后，我们来做一下下面这道难度较大的BFS的题目，其实可以可以看出来，难题一般都是在经典例题的基础上改编的
习题3：走字符迷宫带钥匙-bfs
每个元素的值的含义如下 0-墙，1-路，2-起始位置，3-迷宫的出口，
大写字母-门，小写字母-对应大写字母所代表的门的钥匙
输入描述:
迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N
后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100,
门不超过10扇（A到J，可有多道同一编号的门）。
输出描述:
最短路径的长度，是一个整数
示例1：
输入
5 5
02111
01a0A
01003
01001
01111
输出
7
解释：
1、不经过A，只经过1，则需要9步
2、经过a取钥匙再经过A，则只需要7步
示例2：
输入
6 6
j21111
1b10A0
11a011
111011
JB0011
111113
输出
9
解释：
1、经过a再经过A，需要13步
2、经过b再经过B，需要9步
3、经过j再经过J，需要11步
示例3：
输入
6 6
j21b11
1110A0
11a011
111011
JB0011
111113
输出
11
解释：
1、经过a再经过A，需要13步
2、经过b再经过B，需要13步
3、经过j再经过J，需要11步
示例4：
输入
6 6
b2fgbb
bae0B0
afaBij
cde0cd
0B0Beb
1bj1b3
输出
9
/**
题解：
每一步的状态包含当前坐标、路径长度、【已有门的钥匙】。
其中已有门的钥匙就两种情况：有或没有，那么不妨用二进制表示是否有。
keys=0(D，十进制)=0(B，二进制)，表示一把钥匙都没有
keys=4(D)=100(B),表示有C门的钥匙
keys=5(D)=101(B),表示有A、C门的钥匙
keys=20(D)=10100(B),表示有C、E门的钥匙
v[1][1][0]表示一把钥匙都没有的时候经过（1，1）
v[1][1][4]表示只有C门钥匙的时候经过（1，1）
v[1][1][5]表示有A、C门钥匙的时候经过（1，1）
v[2][2][20]表示有C、E门钥匙的时候经过（2，2）
&：按位与 |：按位或 ^：按位异或 <<：按位左移 >>：按位右移
(keys&(1<<(‘D’-‘A’))==0表示keys中没有D的钥匙。
(keys&(1<<(ch-‘A’))==0表示keys中没有ch的钥匙。
根据队列先进先出的原理，排在队首的路径长度一定最小。
最后进行剪枝。
本题中，一个位置可以走多次，
但是同样的keys状态时如果经过多次同一个点，肯定之后走的时候的累计长度会大于第一次走。
所以不能在同样的keys状态时，经过同一个点，
即每走一步，都要令vis[x][y][keys]==1，把该状态剪枝掉。
*/
import java.util.*;
public class 走字符迷宫带钥匙bfs {
static class node{
int x,y,path;
int keys; //keys用于记录钥匙情况
node(int x,int y,int path,int keys){
this.x=x;
this.y=y;
this.path=path;
this.keys=keys;
}
}
static int MAXV=999;
static int m,n,sp=0;
static char[][] map=new char[MAXV][MAXV];
static int move[][]= {{1,0},{-1,0},{0,1},{0,-1}};
static int[][][] v=new int[101][101][5000];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
m=sc.nextInt();
n=sc.nextInt();
int x=-1,y=-1;
for(int i=0;i<m;i++) {
String s=sc.next();
map[i]=s.toCharArray();
for(int j=0;j<n;j++) {
if(map[i][j]=='2') {
x=i;y=j;
}
}
}
bfs(x,y);
System.out.println(sp);
sc.close();
}
public static void bfs(int x,int y) {
Queue<node> q=new LinkedList<node>();
q.offer(new node(x,y,0,0));
while(!q.isEmpty()) {
node temp=q.poll();
//v[x][y][0] 表示一把钥匙都没有的状态下，经过了（x，y）点
v[temp.x][temp.y][0]=1;
//也可以先移动，后判断，如下所示
for(int i=0;i<4;i++) {
int nx=temp.x+move[i][0];
int ny=temp.y+move[i][1];
int npath=temp.path+1;
int keys=temp.keys;
if(check(nx,ny)) {
char ch=map[nx][ny];
if(ch=='3') {
sp=npath;
return ;
}
//碰到了门,却没有该门的钥匙,则不把该点加入队列,直接走下一步
if(ch>='A'&&ch<='J'&&(keys&(1<<ch-'A'))==0) {
continue;
}
//尝试获取钥匙key,如果是‘a’-‘j’，则之后钥匙加入keys中，如果是‘1’则key仍为0
int key=0;
if(ch>='a'&&ch<='j') {
key=1<<(map[nx][ny]-'a');
}
int nkeys=keys|key;
//假设keys=1001(B),key==10(B),则keys|key=1011,
//v[nx][ny][1011]就表示有A、B、D三把钥匙的时候经过（nx，ny）
if(v[nx][ny][nkeys]==0) {
v[nx][ny][nkeys]=1;
q.offer(new node(nx,ny,npath,nkeys));
}
}
}
}
}
public static boolean check(int x,int y) {
if(x>=0&&y>=0&&x<m&&y<n&&map[x][y]!='0') {
return true;
}else return false;
}
}