如果没有不能走的格子的话，和BZOJ2463一样，直接判断是否能二分图匹配
现在有了一些不能走的格子
黑白染色后求出最大匹配
如果是完备匹配，则无论如何后手都能转移到1*2的另一端，故先手必输
否则的话，将棋子放在不是必须点的点上则先手必赢
证明是这样的：
先手先选一个不在最大匹配里面的点，然后对手有两种情况：
一、走一个在最大匹配里的点，然后有了上面考虑错的那种情况，但是不同的是，如果出现了后手最后走某边达到一个非最大匹配中点，就代表出现了一条增广路，显然因为是最大匹配，所以这种情况是不会出现的，所以这种情况先手必胜。
二、走一个不在最大匹配里的点，然后？诶？这是显然的不对啊！直接增广了，连反向弧神马都不用！！！
于是~~~先手必胜。
于是问题转化为了如何求二分图匹配中的非必须点
求这个的话，直接从一个非匹配点dfs到同一边的匹配点就可以了，注意是可以从一个同侧匹配点到另一个同侧匹配点的
一开始算的时候，我在dfs到一个匹配点就直接return了，思路不清晰的锅
应该是记忆化搜索。。。
为什么关于图的题总是要写很久很久呢 不开森
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,mm; 4 #define N 250005 5 struct Node{ 6 int to,next; 7 }e[N*6]; 8 char s[505][505]; 9 int tot,head[N],idx[N],idy[N],id[505][505],match[N],m[N],n1,n2,t1,t2,ans; 10 int h[]={-1,0,1,0}; 11 int l[]={0,-1,0,1}; 12 bool vis[N],v[N],flag; 13 void add(int x,int y){ 14 e[++tot]=(Node){y,head[x]};head[x]=tot; 15 e[++tot]=(Node){x,head[y]};head[y]=tot; 16 } 17 bool dfs(int x){ 18 for(int i=head[x];i;i=e[i].next) 19 if(!vis[e[i].to]){ 20 vis[e[i].to]=1; 21 if(!match[e[i].to]||dfs(match[e[i].to])){ 22 match[e[i].to]=x;m[x]=e[i].to;return 1; 23 } 24 } 25 return 0; 26 } 27 void dfsz(int x){ 28 v[x]=1; 29 for(int i=head[x];i;i=e[i].next){ 30 if(!v[match[e[i].to]])dfsz(match[e[i].to]); 31 } 32 } 33 void dfsy(int x){ 34 v[x]=1; 35 for(int i=head[x];i;i=e[i].next){ 36 if(!v[m[e[i].to]])dfsy(m[e[i].to]); 37 } 38 } 39 int main(){ 40 scanf("%d%d",&n,&mm); 41 for(int i=1;i<=n;i++){ 42 scanf("%s",s[i]+1); 43 for(int j=1;j<=mm;j++)if(s[i][j]!='#') 44 if((i+j)%2==0)n2++;else n1++; 45 } 46 t1=0;t2=n1; 47 for(int i=1;i<=n;i++) 48 for(int j=1;j<=mm;j++)if(s[i][j]!='#'&&(i+j)%2){ 49 if(!id[i][j])id[i][j]=++t1,idx[t1]=i,idy[t1]=j; 50 for(int k=0;k<4;k++){ 51 int x=i+h[k],y=j+l[k]; 52 if(x&&y&&x<=n&&y<=mm&&s[x][y]!='#'){ 53 if(!id[x][y])id[x][y]=++t2,idx[t2]=x,idy[t2]=y; 54 add(id[i][j],id[x][y]); 55 } 56 } 57 } 58 59 for(int i=1;i<=n1;i++){ 60 memset(vis,0,sizeof(vis)); 61 if(dfs(i))ans++; 62 } 63 if(ans==n1&&ans==n2){puts("LOSE");return 0;} 64 65 for(int i=1;i<=n1;i++)if(!m[i])dfsz(i); 66 for(int i=n1+1;i<=n1+n2;i++)if(!match[i])dfsy(i); 67 // for(int i=1;i<=t2;i++)cout<<i<<' '<<v[i]<<endl; 68 puts("WIN"); 69 for(int i=1;i<=n;i++) 70 for(int j=1;j<=mm;j++) 71 if(v[id[i][j]])printf("%d %d ",i,j); 72 return 0; 73 }
1443: [JSOI2009]游戏Game
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 964 Solved: 431
[Submit][Status][Discuss]
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。