UVA 12530 Game of Tiles （二分图完备匹配，博弈）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：给出一个n*m的格子。有一些障碍物。两人轮流，第一个人先选定某个位置，后一个人只能在前一个人选的位置相邻的位置。不能移动者输。不能选择已经选过的位置 。http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3975 同样还是2012年lartin america的题。。。第一次接触这种博弈。大致做法是这样的：对于某一个连通块，当第一个选定位置之后，根据相邻的染色可以发现把所有的位置染成两种颜色，可以构建二分图。如果这个二分图存在完备匹配的话，也就是先手随便在哪下，后手总能找到与其匹配的位置。那么后手必胜。这样以来就是判断所有的连通块是否存在完备匹配。
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#define N 1255#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))using namespace std;struct Node{ int v,next;}e[100005];vector<int>v[N];int n,m;int tot,start[N];int flag[55][55];char str[55][55];int w,b;int way[4][2]={0,1,0,-1,1,0,-1,0};int pre[N];bool mark[N];void add(int u,int v){ e[tot].v=v; e[tot].next=start[u]; start[u]=tot++;}bool dfs_2(int i){ int j; for(j=start[i];j!=-1;j=e[j].next){ int k=e[j].v; if(!mark[k]){ mark[k]=true; if(pre[k]==0||dfs_2(pre[k])){ pre[k]=i; return true; } } } return false;} int match() { int i,count=0; memset(pre,0,sizeof(pre)); for(i=1;i<=w;i++){ mem(mark,false); if(dfs_2(i)) count++; } return count==w;}void dfs(int x,int y,int c,int u){ for(int i=0;i<4;i++){ int xx=x+way[i][0]; int yy=y+way[i][1]; if(xx<0||yy<0||xx>=n||yy>=m||str[xx][yy]=='X') continue; if(c==0){ if(flag[xx][yy]){ add(u,flag[xx][yy]); continue; } flag[xx][yy]=b; add(u,b); dfs(xx,yy,1,b++); } else{ if(flag[xx][yy]) continue; flag[xx][yy]=w; dfs(xx,yy,0,w++); } }}bool slove(int x,int y){ w=2;b=1; mem(start,-1); tot=0; flag[x][y]=1; dfs(x,y,0,1); w--;b--; if(w!=b) return false; return match();}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ mem(flag,0); for(int i=0;i<n;i++) scanf("%s",str[i]); bool ans=true; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(str[i][j]=='X'||flag[i][j]) continue; if(!slove(i,j)) ans=false; } } printf("%d\n",ans?2:1); } return 0;}