HDU 3085 Nightmare II双方向bfs難易度:2

http://acm.hdu.edu.cn/showproblem.php?pid=3085
良い双方向bfsを出して、カードの時間、普通のbfsはタイムアウトします
問題の内容:
1.滞在可能
2.ghost壁を無視
3.ある地点にghostがあるかどうか、到着しようとしたとき(t)、出発しようとしたとき(t+1)を2回チェックする必要がある.
プログラミングで注意しなければならないのは、
二人が合流する時、出発する時を検査する必要はありません.
Mは3歩歩けますが、この3歩の間に到着できるかどうかをチェックするだけです(t)
問題点:1.検査時間の処理が不明確である
2.通常bfsはタイムアウトする
3.双方向bfsはある時間を完全に処理しなければならない.そうしないと現れる.
a.女の子はすでにプログラムを終了して自動的に終了した(que[0].empty()&!que[1].empty()
b.女の子の歩数が多いので最適解ではない場合

#include <cstdio>

#include <algorithm>

#include <queue>

using namespace std;

const int inf =0x3fffffff;

const int maxn=1e3+3;

char maz[maxn][maxn];

int n,m;

struct pnt

{

    int x,y;

    pnt()

    {

        x=y=0;

    }

    pnt(int tx,int ty):x(tx),y(ty) {}

} z[2],b,g;

typedef pair<pnt,int> P;

int zn;





bool ok(int x,int y,int time)

{

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

    {

        int h=abs(x-z[i].x)+abs(y-z[i].y);

        if(h<=2*time)

        {

            return false;

        }

    }

    return true;

}



int dg[maxn][maxn],db[maxn][maxn];

queue<pnt> que[2];

const int dx[4]= {1,-1,0,0};

const int dy[4]= {0,0,1,-1};

bool in(int x,int y)

{

    return x>=0&&x<n&&y>=0&&y<m&&maz[x][y]!='X';

}

int tempt(int step,int s,int cnt)

{

    int sz=que[s].size();

    while(sz--)

    {

        pnt f=que[s].front();que[s].pop();

        if(!ok(f.x,f.y,step))continue;

        for(int di=0; di<4; di++)

        {

            pnt t=pnt(f.x+dx[di],f.y+dy[di]);

            if(in(t.x,t.y)&&ok(t.x,t.y,step))

            {

                if(s)

                {

                    if(db[t.x][t.y]>step)

                    {

                        db[t.x][t.y]=step;

                        if(dg[t.x][t.y]!=inf)

                            return step;

                        que[s].push(t);

                    }

                }

                else

                {

                    if(dg[t.x][t.y]>step)

                    {

                        dg[t.x][t.y]=step;

                        if(db[t.x][t.y]!=inf)

                            return step;

                        que[s].push(t);

                    }

                }

            }

        }

    }

    return -1;

}



int bfs()

{

    while(!que[0].empty())que[0].pop();

    while(!que[1].empty())que[1].pop();



    que[0].push(g);

    que[1].push(b);

    int step=0;

    while(!que[0].empty()&&!que[1].empty())

    {

        step++;

        int tmp;

        if((tmp=tempt(step,0,0))!=-1)return tmp;

        if((tmp=tempt(step,1,1))!=-1)return tmp;

        if((tmp=tempt(step,1,2))!=-1)return tmp;

        if((tmp=tempt(step,1,3))!=-1)return tmp;

    }

    return -1;

}



void init()

{

    zn=0;

    for(int i=0; i<n; i++)fill(dg[i],dg[i]+m,inf);

    for(int i=0; i<n; i++)fill(db[i],db[i]+m,inf);

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int ti=1; ti<=T; ti++)

    {

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

        init();

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

        {

            scanf("%s",maz[i]);

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

            {

                if(maz[i][j]=='Z')

                {

                    z[zn++]=pnt(i,j);

                }

                else if(maz[i][j]=='G')

                {

                    g=pnt(i,j);

                    dg[g.x][g.y]=0;

                }

                else if(maz[i][j]=='M')

                {

                    b=pnt(i,j);

                    db[b.x][b.y]=0;

                }

            }

        }

        int ans=bfs();

        printf("%d
",ans);

    }

    return 0;

}