Lisa
一个疯狂的双向bfs
压缩一状态，用一个8位int，其中每2位表示一个坐标，这样最差情况下开88888888的int数组，太荒谬了，那就换成一个map，存储状态
这四个球没有区别，所以我们保存状态按照一个固定的顺序保存就可以了
然后就是繁琐的步骤
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
map<int,int> ma;
queue<int> q1,q2;
int now;
int x;
char c;
int vis[9][9];
pair<int,int> cnt[5];
int mx[5]={0,0,1,-1};
int my[5]={1,-1,0,0};
void bfs1(){
int le=q1.size();
while(le--){
int now=q1.front();
q1.pop();
int tem=1;
int x,y;
for(int i=1;i<=4;++i){
if(i==1){
x=now%10;
y=now/10%10;
}else{
tem*=100;
x=now/tem%10;
y=now/tem/10%10;
}
vis[x][y]=1;
cnt[i].first=x;
cnt[i].second=y;
}
int tx;
int ty;
tem=1;
for(int i=1;i<=4;++i){
for(int j=1;j<=4;++j){
tx=cnt[i].first;
ty=cnt[i].second;
while(vis[tx][ty]){
tx+=mx[j-1];
ty+=my[j-1];
}
if(tx<=0||tx>8||ty<=0||ty>8){
continue;
}
int ns=0;
vis[tx][ty]=1;
vis[cnt[i].first][cnt[i].second]=0;
for(int ii=1;ii<=8;++ii){
for(int jj=1;jj<=8;++jj){
if(vis[ii][jj]){
ns=ns*100+jj*10+ii;
}
}
}
vis[cnt[i].first][cnt[i].second]=1;
vis[tx][ty]=0;
if(ma[ns]==1){
continue;
}
if(ma[ns]==2){
printf("YES");
exit(0);
}
ma[ns]=1;
q1.push(ns);
}
}
for(int i=1;i<=4;++i){
vis[cnt[i].first][cnt[i].second]=0;
}
}
}
void bfs2(){
int le=q2.size();
while(le--){
int now=q2.front();
q2.pop();
int tem=1;
int x,y;
for(int i=1;i<=4;++i){
if(i==1){
x=now%10;
y=now/10%10;
}else{
tem*=100;
x=now/tem%10;
y=now/tem/10%10;
}
vis[x][y]=1;
cnt[i].first=x;
cnt[i].second=y;
}
int tx;
int ty;
tem=1;
for(int i=1;i<=4;++i){
for(int j=1;j<=4;++j){
tx=cnt[i].first;
ty=cnt[i].second;
while(vis[tx][ty]){
tx+=mx[j-1];
ty+=my[j-1];
}
if(tx<=0||tx>8||ty<=0||ty>8){
continue;
}
int ns=0;
vis[tx][ty]=1;
vis[cnt[i].first][cnt[i].second]=0;
for(int ii=1;ii<=8;++ii){
for(int jj=1;jj<=8;++jj){
if(vis[ii][jj]){
ns=ns*100+jj*10+ii;
}
}
}
vis[cnt[i].first][cnt[i].second]=1;
vis[tx][ty]=0;
if(ma[ns]==2){
continue;
}
if(ma[ns]==1){
printf("YES");
exit(0);
}
ma[ns]=2;
q2.push(ns);
}
}
for(int i=1;i<=4;++i){
vis[cnt[i].first][cnt[i].second]=0;
}
}
}
int y;
int main(){
for(int i=1;i<=4;++i){
cin>>x>>y;
vis[x][y]=1;
}
now=0;
int mr=1;
for(int ii=1;ii<=8;++ii){
for(int jj=1;jj<=8;++jj){
if(vis[ii][jj]){
now=now*100+jj*10+ii;
vis[ii][jj]=0;
}
}
}
q1.push(now);
ma[now]=1;
now=0;
for(int i=1;i<=4;++i){
cin>>x>>y;
vis[x][y]=1;
}
mr=1;
for(int ii=1;ii<=8;++ii){
for(int jj=1;jj<=8;++jj){
if(vis[ii][jj]){
now=now*100+jj*10+ii;
vis[ii][jj]=0;
}
}
}
q2.push(now);
ma[now]=2;
for(int i=1;i<=8;++i){
if(i&1){
bfs1();
}else{
bfs2();
}
}
cout<<"NO";
return 0;
}