这次整理了一下广度优先搜索的框架，以后可以拿来直接用了。TjuOj1140是一个三维的迷宫题，在BFS时我增加了一个控制数组，用来对队列的出队进行控制，确保每次出队的结点均为同一步长的结点，个人认为比较适合这种迷宫搜索题。
BFS部分的代码如下：
int BFS ( node S , node T )
{
int s = ; //充当指针作用
memset(n,,sizeof(n));
n[s] = ; //初始化当前距离为1的点数为1（即原点）
node now = S;
visit[now.z][now.y][now.x] = ;
node temp;
queue<node> Q;
Q.push(now);
while( !Q.empty() ){
for(int j = ; j < n[s] ; j++ ){ //依次弹出所有距离为s的方块，进行四周搜索；
now = Q.front();
Q.pop();
for(int i = ; i < ;i++){ //向6个方向探索是否有通路
temp.x = now.x + dx[i];
temp.y = now.y + dy[i];
temp.z = now.z + dz[i];
if( visit[temp.z][temp.y][temp.x] == && inmap(temp) ){ //防止越界访问
temp.ch = maze[temp.z][temp.y][temp.x];
if (temp.ch == "E")
return s;
if (temp.ch == "."){ //如果探索到通路，将该通路标记为(当前距离+1) ,压入队列；
n[s + ]++; //(当前距离+1)的方块个数++
visit[temp.z][temp.y][temp.x] = ;
Q.push(temp);
}
}
}
}
s++;
}
return ;
}
题目比较好理解，从S出发找E（但不一定有解），原文如下：
Is an escape possible? If yes, how long will it take?
Input Specification
The input file consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output Specification
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5
S....
.###.
.##..
###.# #####
#####
##.##
##... #####
#####
#.###
####E 1 3 3
S##
#E#
### 0 0 0
Sample Output
Escaped in 11 minute(s).
Trapped!
/*
* 1140_Dungeon Master.cpp
*
* Created on: 2018年11月14日
* Author: Jeason
*/ #include <iostream>
#include <stdio.h>
#include <cstring>
#include <sstream>
#include <queue>
#define N 70
using namespace std;
int levels,rows,columns;
char maze[N][N][N];
int visit[N][N][N];
int n[ ] = {}; //用于记录每个距离的方块个数；
string line;
int dx[] = {,-,,,,};
int dy[] = {,,,-,,};
int dz[] = {,,,,,-}; struct node {
int x,y,z;
string ch;
}; bool inmap(node A) {
if(A.x < || A.x >= columns) return false;
if(A.y < || A.y >= rows) return false;
if(A.z < || A.z >= levels) return false;
return true;
} int BFS(node S,node T)
{
int s = ; //充当指针作用
memset(n,,sizeof(n));
n[s] = ; //初始化当前距离为1的点数为1（即原点）
node now = S;
visit[now.z][now.y][now.x] = ;
node temp;
queue<node> Q;
Q.push(now);
while( !Q.empty() ){
for(int j = ; j < n[s] ; j++ ){ //依次弹出所有距离为s的方块，进行四周搜索；
now = Q.front();
Q.pop();
for(int i = ; i < ;i++){ //向6个方向探索是否有通路
temp.x = now.x + dx[i];
temp.y = now.y + dy[i];
temp.z = now.z + dz[i];
if( visit[temp.z][temp.y][temp.x] == && inmap(temp) ){ //防止越界访问
temp.ch = maze[temp.z][temp.y][temp.x];
if (temp.ch == "E")
return s;
if (temp.ch == "."){ //如果探索到通路，将该通路标记为(当前距离+1) ,压入队列；
n[s + ]++; //(当前距离+1)的方块个数++
visit[temp.z][temp.y][temp.x] = ;
Q.push(temp);
}
}
}
}
s++;
}
return ;
} int main()
{
node S,T;
cin >> levels >> rows >> columns; while( (levels != )&&(rows != )&&(columns != ) ){
memset(maze, , sizeof(maze)); //读入数据；
memset(visit, , sizeof(visit));
for(int i = ;i < levels ;i++){
for(int j = ;j < rows ;j++){
cin >> line;
for(int k = ;k < columns ;k++){
maze[i][j][k] = line[k];
if(line[k] == 'S'){ //找起点
S.z = i; S.x = k; S.y = j;
S.ch = "S";
}
}
}
}
int minutes = BFS( S, T );
if(minutes != )
cout << "Escaped in "<< minutes << " minute(s)."<< endl;
else
cout << "Trapped!" <<endl;
// for(int i = 0;i < levels ;i++){ //输出地图
// for(int j = 0;j < rows ;j++){
// for(int k = 0;k < columns ;k++){
// cout << maze[i][j][k];
// }
// cout << endl;
// }
// cout << endl;
// }
cin >> levels >> rows >> columns;
} return ;
} /* Sample Input
3 4 5
S....
.###.
.##..
###.# #####
#####
##.##
##... #####
#####
#.###
####E 1 3 3
S##
#E#
### 0 0 0
Sample Output
Escaped in 11 minute(s).
Trapped!
*/