题目大意：给你一个8*8的棋盘，上面有四个棋子，给你一个初始排布，一个目标排布，每次移动，可以把一个棋子移动到一个相邻的空位，或者跨过1个相邻的棋子，在保证棋子移动不超过8次的情况下，问能否把棋盘上的棋子由初始排布变成目标排布
8*8的棋盘，刚好不爆ull，状压那些位置有棋子
然后从初始状态开始，暴搜出当前状态下，移动一个棋子之后所有可能到达的状态
直接搜，总状态数是8^8，此外还有常数，会爆
由于给定了目标排布，考虑meet in middle
从起始状态和目标状态各搜4步即可
为了防止爆栈，同时为了好写好调，最好用bfs
具体实现呢，可以开两个队列正反同时bfs，搜到合法结果就break掉，可以减少很多常数
开2个map，表示正/反着跑能否到达状态s，如果能到达，则mp[s]=1
以正着搜为例，当前从que1中取出的状态为s，能到达的下一个状态为t，如果t出现在map1中，就不必在推入que1了，如果t出现在map2中，说明存在合法状态，break掉输出YES
代码好长啊..但在搜索题里算短的了
#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NN 5010
#define MM 2000
#define maxn 200
#define ll long long
#define uint unsigned int
#define ull unsigned long long
using namespace std; int id[][];
int xx[]={-,,,};
int yy[]={,,,-};
ull bin[];
int ax[],ay[],bx[],by[];
struct node{
ull s;int c;
friend bool operator < (const node &s1,const node &s2)
{return s1.s<s2.s;}
node(ull s,int c):s(s),c(c){}
node(){}
};
map<ull,int>mp[];
int check(int x,int y,ull s)
{
if(x<||y<||x>||y>)return ;
if(s&bin[id[x][y]]) return ;
return ;
} int main()
{
//freopen("t2.in","r",stdin);
for(int i=;i<=;i++)
for(int j=;j<=;j++)
id[i][j]=*(i-)+j-;
//px[id[i][j]]=i,py[id[i][j]]=j;
bin[]=;
for(int i=;i<=;i++)
bin[i]=bin[i-]<<;
while(scanf("%d%d%d%d",&ax[],&ay[],&ax[],&ay[])!=EOF)
{
scanf("%d%d%d%d",&ax[],&ay[],&ax[],&ay[]);
scanf("%d%d%d%d",&bx[],&by[],&bx[],&by[]);
scanf("%d%d%d%d",&bx[],&by[],&bx[],&by[]);
queue<node>q[];
ull s=,t=;
int cnt=,fx,fy,fl,nt;
for(int i=;i<=;i++)
s|=bin[id[ax[i]][ay[i]]];
mp[][s]=;
q[].push(node(s,));s=;
for(int i=;i<=;i++)
s|=bin[id[bx[i]][by[i]]];
mp[][s]=;
q[].push(node(s,));
int ans=,c,x,y;
while((!q[].empty()||!q[].empty())&&!ans)
{
if(!q[].empty())
{
node K=q[].front();q[].pop();
s=K.s,c=K.c;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
if(!(s&bin[id[i][j]])) continue;
for(int k=;k<;k++)
{
x=i+xx[k],y=j+yy[k];
fl=check(x,y,s);
if(!fl) continue;
if(fl==){
x+=xx[k],y+=yy[k];
if(check(x,y,s)!=) continue;
}
t=(s^bin[id[i][j]])|bin[id[x][y]];
if(mp[].find(t)!=mp[].end())
continue;
if(mp[].find(t)!=mp[].end())
{ans=;break;}
mp[][t]=;
if(c<) q[].push(node(t,c+));
if(ans==) break;
}
}
}
if(!q[].empty())
{
node K=q[].front();q[].pop();
s=K.s,c=K.c;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
if(!(s&bin[id[i][j]])) continue;
for(int k=;k<;k++)
{
x=i+xx[k],y=j+yy[k];
fl=check(x,y,s);
if(!fl) continue;
if(fl==){
x+=xx[k],y+=yy[k];
if(check(x,y,s)!=) continue;
}
t=(s^bin[id[i][j]])|bin[id[x][y]];
if(mp[].find(t)!=mp[].end())
continue;
if(mp[].find(t)!=mp[].end())
{ans=;break;}
mp[][t]=;
if(c<) q[].push(node(t,c+));
if(ans==) break;
}
}
}
}
if(ans==)
printf("YES\n");
else
printf("NO\n");
mp[].clear();
mp[].clear();
}
return ;
}