详见黄学长的博客 大概就是 所有在模三意义下同余的位置是等价的 可以看成一个点 一个棋子跨过另一个 则可以视为两个棋子合成一个 然后状压记忆化搜索就行了 注意需要预处理边界的情况 有些合成是不合法的 因为会超出边界
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<map> #define cl(x) memset(x,0,sizeof(x)) #define read(x) scanf("%d",&(x)) using namespace std; struct sta{ int a[9]; sta() { cl(a); } int &operator [](int x){ return a[x]; } bool operator < (const sta& B) const{ for (int i=0;i<9;i++) if (a[i]^B.a[i]) return a[i]<B.a[i]; return 0; } }S,T; map<sta,int> f; #define P(x,y) (((x)%3)*3+((y)%3)) int K; int cnt[9]; const int dx[]={0,0,1,-1,1,-1,1,-1}; const int dy[]={1,-1,0,0,1,1,-1,-1}; int n,m; int trans[9][9]; int ed; int u[100],v[100],w[100]; inline void Pre(){ memset(trans,-1,sizeof(trans)); cl(cnt); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ cnt[P(i,j)]++; for (int k=0;k<8;k++) if (i+dx[k]*2>=1 && i+dx[k]*2<=n && j+dy[k]*2>=1 && j+dy[k]*2<=m) trans[P(i,j)][P(i+dx[k],j+dy[k])]=P(i+dx[k]*2,j+dy[k]*2); } ed=0; for (int i=0;i<9;i++) for (int j=0;j<9;j++) if (~trans[i][j]) ed++,u[ed]=i,v[ed]=j,w[ed]=trans[i][j]; } inline int dfs(sta cur){ if (f.count(cur)) return f[cur]; for (int i=1;i<=ed;i++) if (cur[u[i]] && cur[v[i]]){ cur[u[i]]--,cur[v[i]]--,cur[w[i]]++; if (cur[w[i]]>cnt[w[i]]) continue; if (dfs(cur)) return f[cur]=1; cur[u[i]]++,cur[v[i]]++,cur[w[i]]--; } return f[cur]=0; } int main(){ int x,y; freopen("t.in","r",stdin); freopen("t.out","w",stdout); while (~read(K)){ read(n); read(m); read(x); read(y); T=sta(); T[P(x,y)]++; S=sta(); for (int i=1;i<=K;i++) read(x),read(y),S[P(x,y)]++; Pre(); f.clear(); f[T]=1; if (dfs(S)) printf("Yes\n"); else printf("No\n"); } return 0; }