HDU2216Game III（BFS）

新年第一A，2018继续加油，新年快乐

题目大意：给你一张地图，S和Z两个人在地图上找到对方的最短步数。并且两个人每次走的方向都刚好相反。当S越界或者碰壁时呆在原地不动。

解题思路：bfs的正常操作，一个四维图记录两个人走过的地方。注意的地方是，你主要判断的应该是Z而不是S，什么意思呢？就是Z走后再把S“带着走”，例如有这种情况：Z碰壁或者出界无论S什么情况都不能使这种情况入队，此外根据题意都可以。有一点卡了好几次WA，就是结束搜索的条件，理应该两人相邻就可以结束了，但过不了。而加上两人在同一个地方的条件就可以过了。（PS：个人觉得当两人相遇后就结束搜索了，换言之应该不存在两个人到同一个地方的情况，所以条件感觉是多余的。

AC代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

struct node
{
    int x,y,nx,ny,step;
};

int n,m,book[21][21][21][21];
int nex1[4][2]={0,1,1,0,0,-1,-1,0};
int nex2[4][2]={0,-1,-1,0,0,1,1,0};
char map[21][21];
queue<node> que;

bool judge(int x,int y)
{
    if(x<0||x>=n||y<0||y>=m)
        return true;
    return false;
}

bool pan(int x1,int y1,int x2,int y2)
{
    if(x1==x2 && (y1-y2==1||y1-y2==-1||y1-y2==0) || y1==y2 && (x1-x2==1||x1-x2==-1 || x1-x2==0))
        return true;
    return false;
}

int bfs(int x,int y,int nx,int ny)
{
    node now,xia;
    int i;
    while(!que.empty())
        que.pop();
    now.x=x;
    now.y=y;
    now.nx=nx;
    now.ny=ny;
    now.step=0;
    book[x][y][nx][ny]=1;
    que.push(now);
    while(!que.empty())
    {
        now=que.front();
        que.pop();
        for(i=0;i<4;i++)
        {
            xia.x=now.x+nex1[i][0];
            xia.y=now.y+nex1[i][1];
            xia.nx=now.nx+nex2[i][0];
            xia.ny=now.ny+nex2[i][1];
            xia.step=now.step+1;
            if(judge(xia.x,xia.y) || map[xia.x][xia.y]=='X')
                continue;
            if(judge(xia.nx,xia.ny) || map[xia.nx][xia.ny]=='X')
            {
                xia.nx=now.nx;
                xia.ny=now.ny;
            }
            if(book[xia.x][xia.y][xia.nx][xia.ny])
                continue;
            if(pan(xia.x,xia.y,xia.nx,xia.ny))
                return xia.step;
            book[xia.x][xia.y][xia.nx][xia.ny]=1;
            que.push(xia);
        }
    }
    return 0;
}

int main()
{
    int i,j,x,y,nx,ny,res;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        memset(book,0,sizeof(book));
        for(i=0;i<n;i++)
            scanf("%s",map[i]);
        for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            if(map[i][j]=='Z')
                x=i,y=j;
            else if(map[i][j]=='S')
                nx=i,ny=j;
        }
        /*if(pan(x,y,nx,ny))  数据没有这种情况，即开头一开始就相邻或者同位置
        {
            cout<<0<<endl;
            continue;
        }*/
        res=bfs(x,y,nx,ny);
        if(!res)
            cout<<"Bad Luck!"<<endl;
        else
            cout<<res<<endl;
    }
    return 0;
}