Solitaire

题目连接：

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
    
     using namespace std;set
     
       T[2];int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};struct node{    vector
      
       
         >v;};int Bound(pair
        
          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
         
           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
          
            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");}