前置知识：棋盘走路博弈问题

例：LOJ#6033. 「雅礼集训 2017 Day2」棋盘游戏

问题描述：

棋盘上有一个棋子，两个人轮流走，每次可以往相邻四个方向走，不能碰到障碍或已经走过的点，不能走的人输，问先手是否必胜。

分析：

首先将棋盘黑白染色形成二分图，然后将可以互相到达的格子连边。

如果这个二分图有完美匹配，那么先手走匹配边，后手只能走非匹配边，先手必胜。

如果没有完美匹配，那么看起点是否一定在最大匹配中（二分图最大匹配关键点）：

如果起点一定在最大匹配中，那么先手走匹配边，后手只能走非匹配边，如此交替。如果后手走到了一个未匹配的点，那么说明找到了一条交错路，这与起点一定在最大匹配中矛盾，所以后手走到的点一定是匹配点，此时先手必定可以继续，所以先手必胜。

如果起点不一定在最大匹配中，即存在一个最大匹配使得起点不是匹配点，那么先手走一条非匹配边，后手走一条匹配边，如此交替。如果先手走到了一个未匹配点，说明找到了增广路，与最大矛盾，所以先手走到的点一定是匹配点，此时后手必定可以继续，所以后手必胜。

如何判断一个点是否在最大匹配中：

---

回到HDU3446 daizhenyang’s chess

题目描述：

给出棋盘上每个点的可达点，一个棋子，两人轮流走，不能走走过的，不能走的人输，问先手是否必胜。
$n,m\le 15$

题目分析：

问题相当于是把二分图变成了一般图，上面对于是否必胜的分析仍然是适用的，即 起点是否一定在最大匹配中，但是一般图无法像二分图一样求关键点，但是这个题只有一个起点，所以我们先求出全图的最大匹配，然后删去起点，再求出最大匹配与原来的比较即可。
或者可以先求出删去起点的最大匹配，然后加入起点，看是否存在增广路。

Code（注意斜着走不是无限的，只能走它画出来那么远）：

#include<bits/stdc++.h>
#define maxn 255
using namespace std;
int cnt,mat[maxn],pre[maxn],typ[maxn],f[maxn],vis[maxn],tim,q[maxn],l,r;
vector<int>G[maxn];
int find(int x){return !f[x]?x:f[x]=find(f[x]);}
int LCA(int u,int v){
	for(++tim;;swap(u,v)) if(u){
		if(vis[u=find(u)]==tim) return u;
		vis[u]=tim,u=pre[mat[u]];
	}
}
void blossom(int u,int v,int tp){
	for(;find(u)!=tp;u=pre[v]){
		pre[u]=v,v=mat[u];
		if(typ[v]==2) typ[q[++r]=v]=1;
		f[u]=f[v]=tp;
	}
}
bool aug(int s){
	for(int i=1;i<=cnt;i++) typ[i]=pre[i]=f[i]=0;  typ[q[l=r=1]=s]=1;
	while(l<=r){
		int u=q[l++];
		for(int i=G[u].size()-1,v;i>=0;i--) if(typ[v=G[u][i]]!=2&&find(u)!=find(v)){
			if(!typ[v]){
				pre[v]=u,typ[v]=2;
				if(mat[v]) typ[q[++r]=mat[v]]=1;
				else {while(v) u=mat[pre[v]],mat[mat[v]=pre[v]]=v,v=u; return 1;}
			}
			else {int lca=LCA(u,v); blossom(u,v,lca),blossom(v,u,lca);}
		}
	}
	return 0;
}
int n,m,X,id[17][17];
char a[17][17];
int dx[12]={1,-1,0,0,-1,-1,1,1,-2,-2,2,2};
int dy[12]={0,0,1,-1,2,-2,2,-2,1,-1,1,-1};
void add(int p,int x,int y){
	if(x<1||x>n||y<1||y>m||a[x][y]!='.') return;
	G[p].push_back(id[x][y]);
}
int main()
{
	int T; scanf("%d",&T);
	for(int t=1;t<=T;t++){
		scanf("%d%d",&n,&m),cnt=0;
		for(int i=1;i<=n;i++){
			scanf("%s",a[i]+1);
			for(int j=1;j<=m;j++){
				if(a[i][j]!='#') id[i][j]=++cnt;
				if(a[i][j]=='K') X=cnt;
			}
		}
		for(int i=1;i<=cnt;i++) mat[i]=0,G[i].clear();
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]!='#'){
			int p=id[i][j];
			for(int k=1;k<=2;k++) if(k) 
				add(p,i+k,j+k),add(p,i+k,j-k),add(p,i-k,j+k),add(p,i-k,j-k);
			for(int k=0;k<12;k++) add(p,i+dx[k],j+dy[k]);
		}
		for(int i=1;i<=cnt;i++) if(i!=X&&!mat[i]) aug(i);
		printf("Case #%d: daizhenyang %s\n",t,aug(X)?"win":"lose");
	}
}