1401 双向bfs.txt

双向BFS搜索算法

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
struct MAP
{
    int x,y;
};
struct NODE
{
    MAP m[5];
    int map[9][9];
    int lay;
};
MAP m1[5],m2[5];
int map1[9][9],map2[9][9];
__int64 h2;
int dx[9]={0,0,1,0, -1,0,2,0,-2};
int dy[9]={0,1,0,-1, 0,2,0,-2,0};

__int64 getHash(MAP m[])
{
    __int64 i,h=0,t;
    for(i=1;i<=4;i++)
    {
        t=(m[i].x-1) * 8 + m[i].y;
        t=(__int64 )1<<(t-1);
        h=h|t;
    }
    return h;
}
int BFS()
{
    int i,j,x,y,now,yy;
    queue <NODE> qa,qb;
    NODE temp,ttemp;
    map <__int64,int>ma,mb;
    __int64 hh;
    memcpy(temp.m, m1, sizeof(m1));
    memcpy(temp.map, map1,sizeof(map1));
    temp.lay = 0;
    ma[getHash(temp.m)]=1;
    qa.push(temp);

    memcpy(temp.m, m2, sizeof(m2));
    memcpy(temp.map, map2,sizeof(map2));
    temp.lay = 0;
    mb[getHash(temp.m)]=1;
    qb.push(temp);
    now = 1;
    for(int istep=0;istep<4;istep++)
    {
        while(qa.empty()==0)
        {
            ttemp=temp = qa.front();
            if(temp.lay == istep+1)break;
            qa.pop();
            for(i=1;i<=4;i++)
            {
                for(j=1;j<=4;j++)
                {
                    temp = ttemp;
                    x = temp.m[i].x + dx[j];
                    y = temp.m[i].y + dy[j];
                    if(x>=1 && x<=8 && y>=1 && y<=8 && temp.map[x][y]==0)
                    {
                        temp.map[temp.m[i].x][temp.m[i].y]=0;
                        temp.m[i].x = x;
                        temp.m[i].y = y;
                        temp.map[ x][ y]=i;
                        temp.lay++;
                        hh=getHash(temp.m);
                        if(ma.find(hh)!=ma.end())continue;
                        if(mb.find(hh)!=mb.end())return 1;
                        qa.push(temp);
                        ma[hh]=1;
                    }
                }
                for(j=5;j<=8;j++)
                {
                    temp = ttemp;
                    x = temp.m[i].x + dx[j];
                    y = temp.m[i].y + dy[j];
                    if(x>=1 && x<=8 && y>=1 && y<=8 && temp.map[ temp.m[i].x+dx[j]/2 ][ temp.m[i].y+dy[j]/2 ]!=0 && temp.map[x][y] == 0 )
                    {
                        temp.map[temp.m[i].x][temp.m[i].y]=0;
                        temp.m[i].x = x;
                        temp.m[i].y = y;
                        temp.map[ x][ y]=i;
                        temp.lay++;
                        hh=getHash(temp.m);
                        if(ma.find(hh)!=ma.end())continue;
                        if(mb.find(hh)!=mb.end())return 1;

                        qa.push(temp);
                        ma[hh]=1;
                    }
                }
            }
        }
        while(qb.empty()==0)
        {
            ttemp=temp = qb.front();
            if(temp.lay == istep+1)break;
            qb.pop();
            for(i=1;i<=4;i++)
            {
                for(j=1;j<=4;j++)
                {
                    temp = ttemp;
                    x = temp.m[i].x + dx[j];
                    y = temp.m[i].y + dy[j];
                    if(x>=1 && x<=8 && y>=1 && y<=8 && temp.map[x][y]==0)
                    {
                        temp.map[temp.m[i].x][temp.m[i].y]=0;
                        temp.m[i].x = x;
                        temp.m[i].y = y;
                        temp.map[ x][ y]=i;
                        temp.lay++;
                        hh=getHash(temp.m);
                        if(mb.find(hh)!=mb.end())continue;
                        if(ma.find(hh)!=ma.end())return 1;
                        qb.push(temp);
                        mb[hh]=1;
                    }
                }
                for(j=5;j<=8;j++)
                {
                    temp = ttemp;
                    x = temp.m[i].x + dx[j];
                    y = temp.m[i].y + dy[j];
                    if(x>=1 && x<=8 && y>=1 && y<=8 && temp.map[ temp.m[i].x+dx[j]/2 ][ temp.m[i].y+dy[j]/2 ]!=0 && temp.map[x][y] == 0 )
                    {
                        temp.map[temp.m[i].x][temp.m[i].y]=0;
                        temp.m[i].x = x;
                        temp.m[i].y = y;
                        temp.map[ x][ y]=i;
                        temp.lay++;
                        hh=getHash(temp.m);
                        if(mb.find(hh)!=mb.end())continue;
                        if(ma.find(hh)!=ma.end())return 1;
                        qb.push(temp);
                        mb[hh]=1;
                    }
                }
            }
        }
    }
    return 0;
}
int main()
{
    int i;
    while(scanf("%d%d",&m1[1].x,&m1[1].y)!=EOF)
    {
        memset(map1,0,sizeof(map1));
        memset(map2,0,sizeof(map2));
        map1[m1[1].x][m1[1].y] = 1;
        for(i=2;i<=4;i++)
        {
            scanf("%d%d",&m1[i].x,&m1[i].y);
            map1[m1[i].x][m1[i].y] = i;
        }
        for(i=1;i<=4;i++)
        {
            scanf("%d%d",&m2[i].x,&m2[i].y);
            map2[m2[i].x][m2[i].y] = i;
        }
        h2=getHash(m2);
        if(BFS()==1) printf("YES\n");
        else printf("NO\n");
    }
}