搜索问题poj 2251BFS问题
题目大意：这题是一个三维的迷宫题目，其中用'.'表示空地，'#'表示障碍物，'S'表示起点，'E'表示终点，求从起点到终点的最小移动次数，解法和二维的类似，只是在行动时除了东南西北移动外还多了上下。对于题目给出数据的含义就是输入l，r，c，分别代表迷宫有l层，每层长宽分别是c，r。
解题思路：我认为重要的地方一是在于初期的建模，初始想想有一个长宽高都为30的大3d迷宫，根据输入的l，r，c来决定使用的这个大迷宫的空间到底是多少。二是后面对行走路径的判断（即如何判断哪些路是可以走的），某个点可以走的条件——这个点以前没有走过；这个点没有超过迷宫的范围；这个点对应的字符时‘.’或者是'E'(特别是对E的判断，我就忘掉了)。最后，在做题过程中如果用到了队列这个数据结构，在用完之后一定要记得清空，在这个问题上让我贡献了n个WA，还是太水，牢记~~
这道题比较坑爹的一个地方是网上很多资料都将其总结到DFS搜索中，这也太不靠谱了，尼玛非常费劲。
对于数据以可以这样移动
(1,1,1)->(1,1,2)->(1,1,3)->(1,1,4)->(1,1,5)->(1,2,5)
->(1,3,5)->(1,3,4)->(1,4,4)->(2,4,4)->(2,4,5)->(3,4,,5)
共11步就可以到达终点 对于数据二明显不能到达，则输出Trapped
这题用BFS解，每次去队首元素，如果是终点则输出结果移动的次数，否则，从该点开始分别向东南西北上下移动（如果可以走的话）并继续搜，如果到队列为空还没搜到解法，则说明无解。
?
代码如下：
#include <iostream>#include <queue>using namespace std;char ddd[31][31][31];int flag;int l,r,c;struct xyz{ int x; int y; int z;}s,e;struct cd{ int vis; int num; int x; int y; int z;}cddd[31][31][31];void init(){ for(int i = 0;i < 31;i++) for(int j = 0;j < 31;j++) for(int k = 0;k < 31;k++) { cddd[i][j][k].num = 0; cddd[i][j][k].vis = 0; cddd[i][j][k].x = i; cddd[i][j][k].y = j; cddd[i][j][k].z = k; } flag = 0;}int main(){ int i,j,k; queue <cd> q; while(scanf("%d%d%d",&l,&r,&c)!= EOF&&l!=0&&r!=0&&c!=0) { init(); for(i = 0;i < l;i++) for(j = 0;j < r;j++) { /* scanf("%s",ddd[i][j]);*/cin>>ddd[i][j]; for(k = 0;k < c;k++) { if(ddd[i][j][k] == 'S') { s.x = i; s.y = j; s.z = k; } if(ddd[i][j][k] == 'E') { e.x = i; e.y = j; e.z = k; } } } q.push(cddd[s.x][s.y][s.z]); cddd[s.x][s.y][s.z].vis = 1; while(!q.empty()) { cd front = q.front(); int cx = front.x; int cy = front.y; int cz = front.z; if(cddd[e.x][e.y][e.z].vis) { flag = 1; break; } q.pop(); if(!cddd[cx + 1][cy][cz].vis && cx + 1 < l && ddd[cx + 1][cy][cz] == '.' || ddd[cx + 1][cy][cz] == 'E')//一定要记得某个点可以走那么这个点也有可能是"E" { q.push(cddd[cx + 1][cy][cz]); cddd[cx + 1][cy][cz].num += cddd[cx][cy][cz].num + 1; cddd[cx + 1][cy][cz].vis = 1; } if(!cddd[cx - 1][cy][cz].vis && cx - 1 >= 0 && ddd[cx - 1][cy][cz] == '.' || ddd[cx - 1][cy][cz] == 'E') { q.push(cddd[cx - 1][cy][cz]); cddd[cx - 1][cy][cz].num += cddd[cx][cy][cz].num + 1; cddd[cx - 1][cy][cz].vis = 1; } if(!cddd[cx][cy + 1][cz].vis && cy + 1 < r && ddd[cx][cy + 1][cz] == '.' || ddd[cx][cy + 1][cz] == 'E') { q.push(cddd[cx][cy + 1][cz]); cddd[cx][cy + 1][cz].num += cddd[cx][cy][cz].num + 1; cddd[cx][cy + 1][cz].vis = 1; } if(!cddd[cx][cy - 1][cz].vis && cy - 1 >= 0 && ddd[cx][cy - 1][cz] == '.' || ddd[cx][cy - 1][cz] == 'E') { q.push(cddd[cx][cy - 1][cz]); cddd[cx][cy - 1][cz].num += cddd[cx][cy][cz].num + 1; cddd[cx][cy - 1][cz].vis = 1; } if(!cddd[cx][cy][cz + 1].vis && cz + 1 < c && ddd[cx][cy][cz + 1] == '.' || ddd[cx][cy][cz + 1] == 'E') { q.push(cddd[cx][cy][cz + 1]); cddd[cx][cy][cz + 1].num += cddd[cx][cy][cz].num + 1; cddd[cx][cy][cz + 1].vis = 1; } if(!cddd[cx][cy][cz - 1].vis && cz - 1 >= 0 && ddd[cx][cy][cz - 1] == '.' || ddd[cx][cy][cz - 1] == 'E') { q.push(cddd[cx][cy][cz - 1]); cddd[cx][cy][cz - 1].num += cddd[cx][cy][cz].num + 1; cddd[cx][cy][cz - 1].vis = 1; } } while(!q.empty()) q.pop();//一定记得队列用完要清空！ if(flag) printf("Escaped in %d minute(s).\n",cddd[e.x][e.y][e.z].num); else printf("Trapped!\n"); } return 0;}?
关于搜索问题还有很多地方不明白，以后还得自行研究！！
?
?
?