首先要思考的问题肯定是,什么点可以是ans,
不难想到对图黑白染色,假如一个棋子不管怎么走,都只能走到和它同色的点上时,这就是一个ans
再考虑,每次棋子的移动都是黑白相间的
再考虑,黑白染色是可以构成一个二分图的
不难想到,二分图上的增广路。
于是第一问就很好解决,我们构建二分图做最大匹配,
如果所有的黑点和白点都匹配了,那么一定不存在,否则一定存在。
为什么呢?
我们知道,如果这个匹配是二分图的最大匹配,那么图中一定不存在增广路;
而增广路是指从非匹配边最终走到非匹配边(非匹配边比匹配边数多1);
假存在一个未被匹配的点,那么小AA将棋子放在这个点上,
那么下一步小YY要么没法走,要么只能走到一个匹配过的点上,走了一条非匹配边。
那么小AA这要走这个点的匹配边,那下一步小YY要么没法走,要么只能走一条非匹配边
这样下去,我们知道是不存在增广路的,那么最后一步一定走的是匹配边——即小AA走最后一步
所以,只要最大匹配中存在未匹配点,那么这个点就是答案之一;
那答案是不是只有这些点呢?
不是,因为最大匹配不止一种,可以有其他点在最大匹配中未被匹配;
考虑到这样一种情况,我们从一个未匹配点k出发,如果走到了一个被匹配点i,记i原来匹配的点为j
如果我们仅仅改变让i和k匹配,而不和j匹配,那么这样并没有改变最大匹配的数目,而又找到了一个新的点他可以不被匹配
那么这个点显然也是ans
所以,我们做完最大匹配后,我们只要从未被匹配点按未匹配边,匹配边相间dfs下去,找到的所有和起点属于同一点集的点也是ans,问题得解
const dx:array[..] of integer=(,,-,);
dy:array[..] of integer=(,-,,);
type node=record
point,next:longint;
end; var a:array[..,..] of longint;
edge:array[..] of node;
ty,p,cx,cy,wx,wy:array[..] of longint;
v:array[..] of boolean;
k,len,x,y,i,j,n,m,w,r,t:longint;
s:string; procedure add(x,y:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end; function find(x:longint):longint; //匈牙利
var i,y:longint;
begin
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
v[y]:=true;
if (cy[y]=-) or (find(cy[y])=) then
begin
cx[x]:=y;
cy[y]:=x;
exit();
end;
end;
i:=edge[i].next;
end;
exit();
end; procedure dfsx(x:longint);
var i,y:longint;
begin
v[x]:=true;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if (cy[y]<>-) and not v[cy[y]] then dfsx(cy[y]);
i:=edge[i].next;
end;
end; procedure dfsy(y:longint);
var i,x:longint;
begin
v[y]:=true;
i:=p[y];
while i<>- do
begin
x:=edge[i].point;
if (cx[x]<>-) and not v[cx[x]] then dfsy(cx[x]);
i:=edge[i].next;
end;
end; begin
fillchar(p,sizeof(p),);
readln(n,m);
for i:= to n do
begin
readln(s);
for j:= to m do
if s[j]='.' then
begin
inc(k);
a[i,j]:=k;
wx[k]:=i;
wy[k]:=j;
ty[k]:=(i+j) mod ; //划分点集
end;
end;
r:=k;
for i:= to n do
for j:= to m do
if ((i+j) mod =) and (a[i,j]>) then
begin
inc(t);
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if a[x,y]> then
begin
add(a[i,j],a[x,y]);
add(a[x,y],a[i,j]);
end;
end;
end;
fillchar(cx,sizeof(cx),);
fillchar(cy,sizeof(cy),); for i:= to r do
if (cx[i]=-) and (ty[i]=) then
begin
fillchar(v,sizeof(v),false);
w:=w+find(i);
end;
if (w=t) and (r-t=t) then
begin
writeln('LOSE');
halt;
end;
writeln('WIN');
fillchar(v,sizeof(v),false);
for i:= to r do
if (cx[i]=-) and (ty[i]=) then dfsx(i);
for i:= to r do
if (cy[i]=-) and (ty[i]=) then dfsy(i);
for i:= to r do
if v[i] then writeln(wx[i],' ',wy[i]);
end.