Solitaire

题目连接：

http://codeforces.com/gym/100231/

Description

给你一个8*8棋盘，里面有4个棋子，每个棋子可以做一下某个操作之一：

1.走向相邻的空格

2.迈过相邻的棋子

然后给你初始状态和结束状态，问你能否得到呢？

Input

第一行给你4个初始状态棋子的坐标

第二行给你4个结束状态棋子的坐标

Output

输出能否从初始状态走到结束状态

Sample Input

4 4 4 5 5 4 6 5

2 4 3 3 3 6 4 6

Sample Output

YES

Hint

题意

题解：

由于是2002年的题，所以大概怎么搜都可以（他们并没有料到10年后的电脑会跑的这么快

我用的是meet in the mid，牺牲空间来换取时间

从终点和起点都搜一遍

这样跑的很快~

代码

#include<bits/stdc++.h>

using namespace std;

set<int> T[2];

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

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

struct node

{

    vector<pair<int,int> >v;

};

int Bound(pair<int,int> x)

{

    if(x.first<1||x.first>8)return 0;

    if(x.second<1||x.second>8)return 0;

    return 1;

}

int Hit(node tmp,pair<int,int> tt)

{

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

        if(tmp.v[i]==tt)

            return 1;

    return 0;

}

int Hash(node tmp)

{

    int res = 0;

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

    {

        res = res*10+tmp.v[i].first;

        res = res*10+tmp.v[i].second;

    }

    return res;

}

void dfs(node st,int step,int flag)

{

    sort(st.v.begin(),st.v.end());

    if(step==4)

    {

        T[flag].insert(Hash(st));

        return;

    }

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

    {

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

        {

            pair<int,int> next = st.v[i];

            next.first += dx[j];

            next.second += dy[j];

            if(Hit(st,next))

            {

                next.first+=dx[j];

                next.second+=dy[j];

            }

            if(!Bound(next))

                continue;

            node t=st;

            t.v[i]=next;

            dfs(t,step+1,flag);

        }

    }

}

int main()

{

    node k[2];

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

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

        {

            int x,y;scanf("%d%d",&x,&y);

            k[i].v.push_back(make_pair(x,y));

        }

    dfs(k[0],0,0);

    dfs(k[1],0,1);

    for(auto it:T[0])

        if(T[1].find(it)!=T[1].end())

            return puts("YES");

    return puts("NO");

}

巴特西

Codeforces Gym 100231F Solitaire 折半搜索