思路：
二分图博弈嘛 找到最大匹配的必须点
跑个网络流 前后DFS一遍
//By SiriusRen #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=105,M=105*105*35,inf=0x3f3f3f3f; int n,m,id[N][N],cnt,T,vis[M/8],jy; char ch[115][115],xx[]={1,-1,0,0},yy[]={0,0,1,-1}; struct Dinic{ int first[M],next[M],v[M],w[M],tot,top,ans[M],color[M],recx[M],recy[M]; void init(){memset(first,-1,sizeof(first));} void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;} void add(int x,int y,int z){Add(x,y,z),Add(y,x,0);} void build(){ init(),T=cnt+1,color[T]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)if(id[i][j]){ recx[id[i][j]]=i,recy[id[i][j]]=j; if((i+j)&1){ add(0,id[i][j],1),color[id[i][j]]=1; for(int k=0;k<4;k++){ int dx=i+xx[k],dy=j+yy[k]; if(id[dx][dy])add(id[i][j],id[dx][dy],1); } } else add(id[i][j],T,1); } flow(); if(!cnt)puts("LOSE"); else{ puts("WIN"); memset(vis,0,sizeof(vis)),dfs(0,1); memset(vis,0,sizeof(vis)),dfs(T,0); sort(ans+1,ans+1+top); for(int i=1;i<=top;i++)printf("%d %d ",recx[ans[i]],recy[ans[i]]); } } bool tell(){ memset(vis,-1,sizeof(vis)); queue<int>q;q.push(0),vis[0]=0; while(!q.empty()){ int t=q.front();q.pop(); for(int i=first[t];~i;i=next[i]) if(vis[v[i]]==-1&&w[i])vis[v[i]]=vis[t]+1,q.push(v[i]); }return ~vis[T]; } int zeng(int x,int y){ if(x==T)return y; int r=0; for(int i=first[x];~i;i=next[i])if(vis[v[i]]==vis[x]+1&&w[i]){ int t=zeng(v[i],min(w[i],y-r)); w[i]-=t,w[i^1]+=t,r+=t; }if(!r)vis[x]=-1; return r; } int flow(){while(tell())while(jy=zeng(0,inf))cnt-=jy*2;} void dfs(int x,int y){ if(color[x]==y)ans[++top]=x; for(int i=first[x];~i;i=next[i])if(w[i]==y&&!vis[v[i]])vis[v[i]]=1,dfs(v[i],y); } }dinic; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%s",ch[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(ch[i][j]=='.')id[i][j]=++cnt; dinic.build(); }