HDU1253:胜利大逃亡

传送门

题意

逃离迷宫

分析

用优先队列和队列都可以，但是我vis数组写在取队列首节点就MLE了，放在放入节点的地方就ac了，看来是一种固定写法，在放入节点的地方判断，可以防止放入无效点到队列，防止队列过大而MLE，一般优先队列要用vis，但是类似胜利大逃亡（续）就不能这么做了

trick

1.迷宫出口可能为墙

2.绝对距离(x+y+z-3)大于t就走不出去

代码

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int n,m,q,ans,ret,t,time;

int a[6][3]=

{

    0,1,0,

    1,0,0,

    0,-1,0,

    -1,0,0,

    0,0,1,

    0,0,-1

};

bool vis[55][55][55],mp[55][55][55];

struct node

{

    int x,y,z,time;

    bool operator<(const node &p)const

    {

        return time>p.time;

    }

};

bool check(int x,int y,int z)

{

    if(x<1||y<1||z<1||x>n||y>m||z>q||mp[x][y][z]||vis[x][y][z]) return 0;return 1;

}

priority_queue<node>pq;

void bfs()

{

    if(mp[n][m][q]) return ;

    if(n+m+q-3>time) return ;

    node tmp={1,1,1,0},p;

    while(!pq.empty()) pq.pop();

    pq.push(tmp);

    memset(vis,0,sizeof(vis));

    vis[1][1][1]=1;

    while(!pq.empty())

    {

        tmp=pq.top();pq.pop();

        if(tmp.x==n&&tmp.y==m&&tmp.z==q) { ans=tmp.time;return ; }

          if(tmp.time==time) continue;

        //printf("%d %d %d %d\n",tmp.x,tmp.y,tmp.z,tmp.time);

        for(int i=0;i<6;++i)

        {

            int xx=tmp.x+a[i][0],yy=tmp.y+a[i][1],zz=tmp.z+a[i][2];

            if(!check(xx,yy,zz)) continue;

            p={xx,yy,zz,tmp.time+1};

            vis[xx][yy][zz]=1;//vis放在这里就ac了QAQ

            pq.push(p);

        }

    }

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d %d %d %d",&n,&m,&q,&time);

        for(int i=1;i<=n;++i)

            for(int j=1;j<=m;++j)

                for(int k=1;k<=q;++k)

                    scanf("%d",&mp[i][j][k]);

        ans=0x3f3f3f3f;

        bfs();

        if(ans==0x3f3f3f3f||ans>time) puts("-1");

        else printf("%d\n",ans);

    }

}