/*
很显然的BFS,没有悬念,只是实现起来有点麻烦
写完才发现,本题中,起点和终点都很明确,可以用双搜
不过我的单搜也没有超时
*/
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

//状态
struct node
{
    char ch[4];//用char类型是为了省空间
    int ceil;
};
//判断两个状态是否为同一状态
int equal(const node& a,const node& b)
{
    int i = 0, j = 0, ans = 0;
    while(i < 4&&j<4)
    {
        if(a.ch[i] == b.ch[j])
        {
            ans++;
            i++;
            j++;
        }
        else if(a.ch[i] < b.ch[j])
            i++;
        else if(a.ch[i] > b.ch[j])
            j++;
    }
    return ans; 
}
queue<node> Q;
map<int, int> M;//避免状态重复
bool m[9][9];

int main()
{
    int a1[8], a2[8], i, j, id;
    node start, end, p, q;
    bool flag;
    while(cin>>a1[0])
    {
        flag = 0;id = 0;
        //输入目标状态
        for(i = 1; i < 8; i++)
            cin>>a1[i];
        //输入初始状态
        for(i = 0; i < 8; i++)
            cin>>a2[i];
        //记录初始状态,每个char存储两位数,分别是横坐标与纵坐标
        for(i = 0; i < 4; i++)
        {
            start.ch[i] = (a2[2*i])*10+a2[2*i+1];
            id = id * 100 + start.ch[i];
        }
        //将四个点按顺序存储,有利于后续操作
        sort(start.ch, start.ch+4);
        start.ceil = 0;
        //同样方法处理目标状态
        for(i = 0; i < 4; i++)
            end.ch[i] = (a1[2*i])*10+a1[2*i+1];
        sort(end.ch, end.ch+4);

        //典型的BFS
        while(!Q.empty())Q.pop();
        M.clear();
        M[id] = 1;
        Q.push(start);
        while(!Q.empty())
        {
            p = Q.front();
            Q.pop();
            if(p.ceil > 8)break;
            int ans = equal(p, end);
            if(ans == 4)
            {
                flag = 1;
                break;
            }
            //优化:如果还能走2步,却有3个棋子没有在目标位置上,肯定不能成功
            if(ans < p.ceil - 4)
                continue;
            memset(m, 0, sizeof(m));
            //析出状态对应的坐标
            for(i = 0; i < 4; i++)
            {
                int temp = (int)p.ch[i];
                m[temp/10][temp%10] = 1;
            }
            //下一步
            for(i = 0; i < 4; i++)
            {
                int temp = (int)p.ch[i];
                int x = temp/10, y = temp%10;
                //上
                q = p;q.ceil++;
                if(x > 1)
                {
                    //下一步是空的,就走下一步
                    if(m[x-1][y] == 0)
                    {
                        q.ch[i] = (x-1)*10+y;
                        sort(q.ch, q.ch+4);
                        id = 0;
                        for(j = 0; j < 4; j++)
                            id = id * 100 + q.ch[j];
                        if(M[id] == 0)
                        {
                            Q.push(q);
                            M[id] = 1;
                        }
                    }
                    //下一步是棋子,下下步是空的,就跳一步
                    else
                    {
                        if(x > 2 && m[x-2][y] == 0)
                        {
                            q.ch[i] = (x-2)*10+y;
                            sort(q.ch, q.ch+4);
                            id = 0;
                            for(j = 0; j < 4; j++)
                                id = id * 100 + q.ch[j];
                            if(M[id] == 0)
                            {
                                Q.push(q);
                                M[id] = 1;
                            }
                        }
                    }
                }
                //下
                q = p;q.ceil++;
                if(x < 8)
                {
                    if(m[x+1][y] == 0)
                    {
                        q.ch[i] = (x+1)*10+y;
                        sort(q.ch, q.ch+4);
                        id = 0;
                        for(j = 0; j < 4; j++)
                            id = id * 100 + q.ch[j];
                        if(M[id] == 0)
                        {
                            Q.push(q);
                            M[id] = 1;
                        }
                    }
                    else
                    {
                        if(x < 7 && m[x+2][y] == 0)
                        {
                            q.ch[i] = (x+2)*10+y;
                            sort(q.ch, q.ch+4);
                            id = 0;
                            for(j = 0; j < 4; j++)
                                id = id * 100 + q.ch[j];
                            if(M[id] == 0)
                            {
                                Q.push(q);
                                M[id] = 1;
                            }
                        }
                    }
                }
                //左
                q = p;q.ceil++;
                if(y > 1)
                {
                    if(m[x][y-1] == 0)
                    {
                        q.ch[i] = x*10+y-1;
                        sort(q.ch, q.ch+4);
                        id = 0;
                        for(j = 0; j < 4; j++)
                            id = id * 100 + q.ch[j];
                        if(M[id] == 0)
                        {
                            Q.push(q);
                            M[id] = 1;
                        }
                    }
                    else
                    {
                        if(y > 2 && m[x][y-2] == 0)
                        {
                            q.ch[i] = x*10+y-2;
                            sort(q.ch, q.ch+4);
                            id = 0;
                            for(j = 0; j < 4; j++)
                                id = id * 100 + q.ch[j];
                            if(M[id] == 0)
                            {
                                Q.push(q);
                                M[id] = 1;
                            }
                        }
                    }
                }
                //右
                q = p;q.ceil++;
                if(y < 8)
                {
                    if(m[x][y+1] == 0)
                    {
                        q.ch[i] = x*10+y+1;
                        sort(q.ch, q.ch+4);
                        id = 0;
                        for(j = 0; j < 4; j++)
                            id = id * 100 + q.ch[j];
                        if(M[id] == 0)
                        {
                            Q.push(q);
                            M[id] = 1;
                        }
                    }
                    else
                    {
                        if(y < 7 && m[x][y+2] == 0)
                        {
                            q.ch[i] = x*10+y+2;
                            sort(q.ch, q.ch+4);
                            id = 0;
                            for(j = 0; j < 4; j++)
                                id = id * 100 + q.ch[j];
                            if(M[id] == 0)
                            {
                                Q.push(q);
                                M[id] = 1;
                            }
                        }
                    }
                }
            }
        }
        if(flag)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

results matching ""

    No results matching ""