题目大意：给定一个矩阵，一些位置有障碍，先手放置在某个位置，后手移动，先手再移动，一个格子只能经过一次，问是否先手必胜

二分图博弈= = 将矩阵建成二分图，考虑二分图博弈的模型：

给定一个二分图，每个点只能走一次，先手选定位置后手走，问是否先手必胜

那么对于任意一个点，如果存在一个最大匹配中这个点没有被匹配，那么先手从这个点开始存在必胜策略

先手放置后，后手无论走到哪个点，先手一定能沿着匹配边走回去

如果不存在匹配边，说明找到了一条增广路，与最大匹配的前提相悖，故一定存在匹配边

当二分图存在完备匹配时先手必败。

这个题还让我们求出先手选择哪些点可以必胜

那么我们做两次最大匹配，每次只考虑左边的点哪些可以必胜

枚举每个未匹配的点，沿着出边->匹配边->出边->匹配边的顺序开始深搜，深搜到的所有左侧的点就是左侧的可选点集。

时间复杂度O(n^2) 虽然数据范围是10000但是匈牙利算法的常数很小 亲测可过

坑比样例- - 别忘了输出WIN。。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; struct abcd{ int to,next; }table[20200]; int head[5050],tot; int m,n,n1,n2; char map[110][110]; int pos[110][110]; bool ans[2][5050]; void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } namespace Bipartite_Graph_Maximum_Match{ int result[5050]; bool state[5050],lonely[5050]; bool Hungary(int x) { int i; for(i=head[x];i;i=table[i].next) { if(state[table[i].to]) continue; state[table[i].to]=1; if( !result[table[i].to] || Hungary(result[table[i].to]) ) { result[table[i].to]=x; return true; } } return false; } void DFS(int x,bool ans[]) { int i; ans[x]=true; for(i=head[x];i;i=table[i].next) if(!ans[result[table[i].to]]) DFS(result[table[i].to],ans); } } using namespace Bipartite_Graph_Maximum_Match; void Initialize() { memset(head,0,sizeof head); tot=0; memset(result,0,sizeof result); memset(lonely,0,sizeof lonely); } int main() { static const int dx[]={0,0,1,-1}; static const int dy[]={1,-1,0,0}; int i,j,k; cin>>m>>n; for(i=1;i<=m;i++) { scanf("%s",map[i]+1); for(j=1;j<=n;j++) if(map[i][j]=='.') pos[i][j]=++(i+j&1?n1:n2); } for(i=1;i<=m;i++) for(j=1;j<=n;j++) if( i+j&1 && map[i][j]=='.' ) for(k=0;k<4;k++) { int x=i+dx[k]; int y=j+dy[k]; if(x<=0||y<=0||x>m||y>n||map[x][y]=='#') continue; Add(pos[i][j],pos[x][y]); } int matches=0; for(i=1;i<=n1;i++) { memset(state,0,sizeof state); if( Hungary(i) ) matches++; else lonely[i]=true; } if( matches==n1 && matches==n2 ) return cout<<"LOSE"<
      
       m||y>n||map[x][y]=='#') continue; Add(pos[i][j],pos[x][y]); } for(i=1;i<=n2;i++) { memset(state,0,sizeof state); if( !Hungary(i) ) lonely[i]=1; } for(i=1;i<=n2;i++) if(lonely[i]) DFS(i,ans[0]); cout<<"WIN"<