VEXOBEN
Vexoben
Jul 13, 2018
It takes 10 minutes to read this article.

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1443

题意

给定一个n*m的棋盘,有些地方有障碍。AA和YY做游戏。AA先在任意位置放一颗棋子,随后YY和AA交替移动棋子,走过的格子不能走,最先不能走的人输。问AA是否有必胜策略。如果有,输出所有可能的放置棋子位置。

n,m<=100

题解

给出题人点赞!

首先,给定一个棋盘,如果将它黑白染色,我们可以得到二分图。

这时可以观察到一个性质:如果AA将棋子放在一个不在最大匹配内的格子上,他是必胜的。

因为YY移动时,它要么不能走,要么移动到一个匹配点上,否则就会与“二分图最大匹配中无增广路”相矛盾。这时AA只要走到相应的匹配点,就可以保证必胜了。

同理可知,如果最大匹配包含了所有的点,那么AA必败。

然后考虑如何输出可行点。一个点是可行点,当且仅当存在一个最大匹配不包含这个点。

下面给出最大流的求解方法:

先求出任意一个最大匹配。从S开始,走cap=1的边,走到所有X部的点都是答案;从T开始,走cap=0的边,走到所有Y部的点都是答案。

可以这样理解:不在最大匹配中的点显然会被走到。而一个最大匹配中的点,需要一个不在最大匹配中的点来代替它。从X部走cap=1的边到Y部,相当于是X部的未匹配点找到一个Y部点。如果这时还能通过cap=1的边走回来,那就是找到了原来和Y部点匹配的X部点。这时就可以用这个点代替那个X部的匹配点。

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
const int u[4]={1,-1,0,0};
const int v[4]={0,0,1,-1};

char s[105];
int a[105][105];
int n,m,E=1,V,S,T,c1,c2,flag=0;
int x[N],y[N],belong[N],vis[N],use[N],ans[N];
int fir[N],nex[N<<1],arr[N<<1],cap[N<<1],dis[N],cur[N<<1];
queue<int> Q;
pair<int,int> pnt[N];
map<pair<int,int>,int> Map;

namespace FastIO {
	template<typename tp> inline void read(tp &x) {
		x=0; register char c=getchar(); register bool f=0;
		for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
		for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
		if(f) x=-x;
	}
	template<typename tp> inline void write(tp x) {
	  if (x==0) return (void) (putchar('0'));
     if (x<0) putchar('-'),x=-x;
     int pr[20]; register int cnt=0;
     for (;x;x/=10) pr[++cnt]=x%10;
     while (cnt) putchar(pr[cnt--]+'0');
	}
	template<typename tp> inline void writeln(tp x) {
		write(x);
		putchar('\n');
	}
}
using namespace FastIO;

inline void Add_Edge(int x,int y,int c) {
	nex[++E]=fir[x];
	fir[x]=E; arr[E]=y; cap[E]=c;
	nex[++E]=fir[y];
	fir[y]=E; arr[E]=x; cap[E]=0;
}

int bfs() {
	memset(dis,0x3f,sizeof(int)*(V+10));
	Q.push(S); dis[S]=0;
	while (!Q.empty()) {
		int x=Q.front(); Q.pop();
		for (int i=fir[x];i;i=nex[i]) {
			if (!cap[i]) continue;
			if (dis[arr[i]]>dis[x]+1) {
				dis[arr[i]]=dis[x]+1;
				Q.push(arr[i]);
			}
		}
	}
	return dis[T]<inf;
}

int dfs(int x,int maxflow) {
	if (x==T||!maxflow) return maxflow;
	int ans=0;
	for (int i=cur[x];i;cur[x]=i=nex[i]) {
		int v=arr[i];
		if (dis[v]==dis[x]+1&&cap[i]) {
			int del=dfs(v,min(maxflow,cap[i]));
			cap[i]-=del; cap[i^1]+=del;
			ans+=del; maxflow-=del;
		}
	}
	return ans;
}

void Solve(int x,int t) {
	vis[x]=1;
	if (belong[x]==t) {
		ans[x]=1;
		if (x!=S&&x!=T) flag=1;
	}
	for (int i=fir[x];i;i=nex[i]) {
		if (cap[i]==t&&!vis[arr[i]]) Solve(arr[i],t);
	}
}

int main() {
	read(n); read(m);
	for (int i=1;i<=n;i++) {
		scanf("%s",s+1);
		for (int j=1;j<=m;j++) a[i][j]=(s[j]=='.');
	}
	S=++V; T=++V;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			if (a[i][j]==0) continue;
			++V; pnt[V]=mp(i,j); Map[mp(i,j)]=V;
			if ((i+j)&1) x[++c1]=V;
			else y[++c2]=V;
		}
	}
	for (int i=1;i<=c1;i++) belong[x[i]]=1;
	for (int i=1;i<=c2;i++) belong[y[i]]=0;
	for (int i=1;i<=c1;i++) Add_Edge(S,x[i],1);
	for (int i=1;i<=c2;i++) Add_Edge(y[i],T,1);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			if ((i+j)%2==0) continue;
			int r=Map[mp(i,j)];
			if (!r) continue;
			for (int k=0;k<4;k++) {
				int t=Map[mp(i+u[k],j+v[k])];
				if (!t) continue;
				Add_Edge(r,t,1);
			}
		}
	}
	while (bfs()) {
		memcpy(cur,fir,sizeof(int)*(V+10));
		dfs(S,inf);
	}
	memset(vis,0,sizeof(vis));
	Solve(S,1); Solve(T,0);
	if (!flag) return 0*puts("LOSE");
	puts("WIN");
	for (int i=3;i<=V;i++) {
		if (ans[i]) {
			write(pnt[i].first); putchar(' '); writeln(pnt[i].second);
		}
	}
	return 0;
}