题目
分析
第一次做这种题，其实很简单。只能经过一次的博弈可以考虑转化为二分图博弈。 棋盘上有黑白色的棋子，可以把这个游戏看作空格在棋子间移动，于是就想到，把棋盘黑白染色，以空格为黑，那么空格的移动轨迹一定是黑白相间的。发现有一些棋子空格是移不过去的，那就是染色与棋子颜色不同的点（由于兔兔白棋先走，所以把空格染成黑色，可以符合要求）。剩下的点，把它们分成两部分，黑色和白色，那么可以组成一个二分图，所有的路径其实就是二分图上的路径，因为不可能有两个白色或黑色的棋子相邻。这个问题转化成了一个二分图上的博弈问题，不能走到重复的点。 对于二分图上的博弈，有一个结论：必胜点必定在最大匹配上。也就是说，如果有多种匹配情况，而一个点在某些情况中在最大匹配中，而在其他情况中不在，那么这个点不是必胜的。 下面说明这个结论： 如果一个点\(x\)一定在最大匹配中，那么当前操作者沿着这个点的匹配边走出去，走到对面的匹配点\(y\)。点\(x\)已经不能再走了，但由于\(x\)必定在最大匹配中，这就说明，删除点\(x\)后点\(y\)找不到一条新的增广路，所以\(y\)能走到的任意下一条边一定是非匹配边，连接着一个匹配点。所以轮到先手时，总是可以在一个匹配点上，它的匹配边连出去的另一个点没有被走过。由于边不可能有无限多，而先手总是有办法走，所以后手一定会输。 所以这题直接记录每一个走到的点是否一定在新图的最大匹配中，如果兔兔走之前在，之后也在，那么她就走错了。注意要把走过的点删掉。
代码
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
int x=0,f=1;
char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int xx[]={-1,0,1,0};
const int yy[]={0,1,0,-1};
const int maxn=51;
const int maxm=maxn*maxn;
char s[maxn][maxn];
bool a[maxn][maxn],alr[maxm],cannot[maxm],able[maxm];
int white[maxm];
int sx,sy,n,m,wrong[maxm],wt=0,match[maxm],all;
struct egde {
int v,nxt;
} e[maxm<<3];
int h[maxm],tot=0;
void add(int u,int v) {
e[++tot]=(egde){v,h[u]};
h[u]=tot;
}
int dis(int ax,int ay,int bx,int by) {
return abs(ax-bx)+abs(ay-by);
}
int ID(int x,int y) {
return (x-1)*m+y;
}
int change(int x) {
return x&1?x+1:x-1;
}
bool dfs(int x) {
for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (!alr[v] && able[v]) {
alr[v]=true;
if (!match[v] || dfs(match[v])) {
match[v]=x;
match[x]=v;
return true;
}
}
return false;
}
bool win[maxm];
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
n=read(),m=read();
all=ID(n,m);
for (int i=1;i<=n;++i) {
scanf("%s",s[i]+1);
for (int j=1;j<=m;++j) if (s[i][j]=='.') sx=i,sy=j;
}
for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) {
int id=ID(i,j);
white[id]=dis(i,j,sx,sy)&1;
if ((s[i][j]=='O' && white[id]) || ((s[i][j]=='X' || s[i][j]=='.') && !white[id])) able[id]=true; else able[id]=false;
}
for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) {
int aid=ID(i,j);
if (!able[aid]) continue;
for (int k=0;k<4;++k) {
int x=xx[k]+i,y=yy[k]+j;
if (x<1 || x>n || y<1 || y>m) continue;
int bid=ID(x,y);
if (able[bid]) {
add(bid,aid),add(aid,bid);
}
}
}
for (int i=1;i<=all;++i) if (!white[i]) {
memset(alr,0,sizeof alr);
dfs(i);
}
int k=read();
for (int i=1;i<=(k<<1);++i) {
int id=ID(sx,sy);
able[id]=false;
if (match[id]) {
int tmp=match[id];
match[id]=match[tmp]=0;
memset(alr,0,sizeof alr);
win[i]=!dfs(tmp);
} else win[i]=false;
sx=read(),sy=read();
}
wt=0;
for (int i=1;i<=k;++i) if (win[i*2-1] && win[i*2]) ++wt;
printf("%d\n",wt);
for (int i=1;i<=k;++i) if (win[i*2-1] && win[i*2]) printf("%d\n",i);
return 0;
}
转载于:https://www.cnblogs.com/owenyu/p/6724636.html
