现在的位置: 首页 > 综合 > 正文

HDOJ–1253–胜利大逃亡【搜索】

2018年04月24日 ⁄ 综合 ⁄ 共 1290字 ⁄ 字号 评论关闭

一道三维BFS题,以前做过一次三维BFS,那次WA出了翔,这次我怀着一次AC的心态小心翼翼的做着,结果这回TLE出翔了。

结果是题面上说要用C++交,G++交会超时。。。我看题时看到了,提交时却给忘了,并且还在想剪枝往里面添,各种TLE。

发现TLE的错误原因后又交了一发WA,发现是我BFS里在while(!q.empty())结束后没有返回语句,加上之后AC了,贴代码吧

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<stdlib.h>
#include<ctime>
#define PI acos(-1)
using namespace std;
int a,b,c,t;
int visit[55][55][55];
int dir[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
int map[55][55][55];

int bfs()
{
    int x,y,z,step,nextstep,xt,yt,zt,i;
    queue<int>q;
    q.push(0);              //放入x
    q.push(0);              //放入y
    q.push(0);              //放入z
    q.push(0);              //放入step;
    visit[0][0][0]=1;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        y=q.front();
        q.pop();
        z=q.front();
        q.pop();
        step=q.front();
        q.pop();
        if(x==a-1&&y==b-1&&z==c-1)
        {
            if(step<=t) return step;
            else    return -1;
        }
        for(i=0;i<6;i++)
        {
            xt=x+dir[i][0];
            yt=y+dir[i][1];
            zt=z+dir[i][2];
            nextstep=step+1;
            if(!visit[xt][yt][zt]&&!map[xt][yt][zt]&&xt>=0&&xt<a&&yt>=0&&yt<b&&zt>=0&&zt<c)
            {
                q.push(xt);
                q.push(yt);
                q.push(zt);
                q.push(nextstep);
                visit[xt][yt][zt]=1;
            }
        }
    }
    return -1;
}
int main()
{
    int i,j,k,n,x;
    scanf("%d",&n);
    while(n--)
    {
        memset(visit,0,sizeof(visit));
        scanf("%d%d%d%d",&a,&b,&c,&t);
        for(i=0;i<a;i++)
            for(j=0;j<b;j++)
                for(k=0;k<c;k++)
                    scanf("%d",&map[i][j][k]);
        printf("%d\n",bfs());
    }
    return 0;
}

抱歉!评论已关闭.