题意
这是一个在n*m的网格图上的博弈。后手先选择一个网格，把棋子放上去，之后轮流操作棋子向相邻的格子移动，每个格子只能让棋子停留一次，同时图中存在一些障碍点。问后手能否赢，若能，问放在哪些格子上能赢。
(1 leqslant n,m leqslant 100)
题解
一道博弈二分图匹配题。
首先对网格图黑白染色，然后相邻格子之间连边跑最大匹配。如果存在完美匹配，那么后手必定输。因为不管棋子放在哪，先手必定沿着匹配边走，然后后手必定沿着非匹配边走，而每个点都被匹配了，那么后手一定将棋子移到一个匹配点上（或者不能移便输了），先手再沿匹配边走，重复这个过程后手便没有胜算。
而一旦存在非匹配点，那么后手胜。因为只要先把棋子先放在一个非匹配点上，先手一定移动到匹配点上（否则两点直接匹配了），然后后手沿着匹配边走，先手又会移动到一个匹配点上（否则这个路径就是匈牙利算法的一个拓展路径，两个非匹配点就可以匹配上了），重复这个过程就行。
然后第二问就是问哪些点不一定要在最大匹配中，我们暂时将其称为非关键点。显然非匹配点不一定要在最大匹配中。然后我们先选择一个非关键点，那么与它相连的点匹配的点，一定也是非关键点，因为最开始选择的那个点可以匹配掉与它们相邻的点，使得它们变成非匹配点，之后直接顺势递归下去即可。
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<algorithm>
using namespace std;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
const int maxn=100;
int n,m,Time;
int vis[maxn+8][maxn+8];
bool can[maxn+8][maxn+8];
char map[maxn+8][maxn+8];
int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*f;
}
struct pos
{
int x,y;
}match[maxn+8][maxn+8];
bool in_map(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]=='.';}
bool extra(int x,int y)
{
for (int i=0;i<4;i++)
{
int sx=x+dx[i],sy=y+dy[i];
if (!in_map(sx,sy)) continue;
if (vis[sx][sy]==Time) continue;
vis[sx][sy]=Time;
if ((match[sx][sy].x==0)||extra(match[sx][sy].x,match[sx][sy].y))
{
match[sx][sy]=(pos){x,y};
match[x][y]=(pos){sx,sy};
return 1;
}
}
return 0;
}
void dfs(int x,int y)
{
if (can[x][y]) return;
can[x][y]=1;
for (int i=0;i<4;i++)
{
int sx=x+dx[i],sy=y+dy[i];
if (!in_map(sx,sy)) continue;
dfs(match[sx][sy].x,match[sx][sy].y);
}
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++) scanf("%s",map[i]+1);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if ((i+j)&1)
{
Time++;
if (map[i][j]=='#') continue;
extra(i,j);
}
bool flag=0;
Time++;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if ((i+j)&1) continue;
if (match[i][j].x) continue;
if (map[i][j]=='#') continue;
flag=1;
dfs(i,j);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if ((i+j)&1)
{
if (match[i][j].x) continue;
if (map[i][j]=='#') continue;
//printf("check:%d %d
",i,j);
flag=1;
dfs(i,j);
}
if (!flag) puts("LOSE");
else
{
puts("WIN");
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (can[i][j])
printf("%d %d
",i,j);
}
return 0;
}