Description
Input
输入数据首先输入两个整数N,M，表示了迷宫的边长。 接下来N行，每行M个字符，描述了迷宫。
Output
若小AA能够赢得游戏，则输出一行"WIN"，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出 每行一个,否则输出一行"LOSE"（不包含引号）。
Sample Input
3 3
.##
...
#.#
.##
...
#.#
Sample Output
WIN
2 3
3 2
2 3
3 2
HINT
对于100%的数据，有1≤n,m≤100。 对于30%的数据，有1≤n,m≤5。
正解：二分图+博弈论。
首先我们可以把这个网格图黑白染色，相邻点连边，变成二分图。
小$AA$是后手，后手要赢的充要条件是起点不一定要在最大匹配中。
如果起点不在最大匹配中，那么和起点相邻的点肯定在最大匹配中。
小$YY$移动以后，小$AA$总能移动到当前点的匹配点，所以小$AA$必胜。
判断一个点是否一定在最大匹配中可以把这个点删掉，再看最大匹配是否变化。
但是在这里如果这样做的话就会$T$，所以我们考虑别的方法。
我们先求一遍最大匹配，然后找到没有匹配的点，它肯定是合法起点。
从这个点开始搜索，直接找相邻点的匹配点，那么这个匹配点肯定也是合法点。
然后一直搜索就能找到所有可行解了。
1 #include <bits/stdc++.h> 2 #define il inline 3 #define RG register 4 #define ll long long 5 #define pos(x,y) ((x-1)*m+(y)) 6 #define N (100005) 7 ?8 using namespace std; 9 10 struct edge{ int nt,to; }g[N];11 12 const int d1[4]={1,0,-1,0};13 const int d2[4]={0,1,0,-1};14 15 int head[N],can[N],vis[N],lk[N],mp[105][105],ok,n,m,num,cnt,ans;16 17 il int gi(){18 ??RG int x=0,q=1; RG char ch=getchar();19 ??while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();20 ??if (ch==‘-‘) q=-1,ch=getchar();21 ??while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();22 ??return q*x;23 }24 25 il char gc(){26 ??RG char ch=getchar();27 ??while (ch!=‘.‘ && ch!=‘#‘) ch=getchar(); return ch;28 }29 30 il void insert(RG int from,RG int to){31 ??g[++num]=(edge){head[from],to},head[from]=num; return;32 }33 34 il int dfs(RG int x){35 ??vis[x]=cnt;36 ??for (RG int i=head[x],v;i;i=g[i].nt){37 ????v=g[i].to; if (vis[v]==cnt) continue; vis[v]=cnt;38 ????if (!lk[v] || dfs(lk[v])){ lk[x]=v,lk[v]=x; return 1; }39 ??}40 ??return 0;41 }42 43 il void find(RG int x){44 ??if (vis[x]==cnt) return; vis[x]=cnt,can[x]=1;45 ??for (RG int i=head[x];i;i=g[i].nt)46 ????if (vis[lk[g[i].to]]!=cnt) find(lk[g[i].to]);47 ??return;48 }49 50 int main(){51 #ifndef ONLINE_JUDGE52 ??freopen("game.in","r",stdin);53 ??freopen("game.out","w",stdout);54 #endif55 ??n=gi(),m=gi();56 ??for (RG int i=1;i<=n;++i)57 ????for (RG int j=1;j<=m;++j) mp[i][j]=gc()==‘.‘;58 ??for (RG int i=1;i<=n;++i)59 ????for (RG int j=1;j<=m;++j){60 ??????if (!mp[i][j]) continue;61 ??????for (RG int k=0,x,y;k<2;++k){62 ????x=i+d1[k],y=j+d2[k]; if (x>n || y>m || !mp[x][y]) continue;63 ????insert(pos(i,j),pos(x,y)),insert(pos(x,y),pos(i,j));64 ??????}65 ????}66 ??for (RG int i=1;i<=n;++i)67 ????for (RG int j=1;j<=m;++j)68 ??????if (mp[i][j] && !lk[pos(i,j)]) ++cnt,dfs(pos(i,j));69 ??for (RG int i=1,x,y;i<=n*m;++i){70 ????x=(i-1)/m+1,y=(i-1)%m+1;71 ????if (mp[x][y] && !lk[i]) ++cnt,find(i);72 ??}73 ??for (RG int i=1,x,y;i<=n*m;++i){74 ????if (!can[i]) continue;75 ????x=(i-1)/m+1,y=(i-1)%m+1;76 ????if (!ok) ok=1,puts("WIN");77 ????printf("%d %d\n",x,y);78 ??}79 ??if (!ok) puts("LOSE"); return 0;80 }bzoj1443 [JSOI2009]游戏Game
原文地址：https://www.cnblogs.com/wfj2048/p/7999974.html