搜索问题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;
}

 

关于搜索问题还有很多地方不明白，以后还得自行研究！！