先对整幅图进行二分图染色，再跑一遍匈牙利算法。如果最大匹配数=点数*2，那么输出WIN。
对于任何一个非必须在最大匹配上的点，即为所求的点。
Program Test375num2;
type arr=record
u,v,next:longint;
end;
const dx:array[..] of longint=(,,-,);
dy:array[..] of longint=(,-,,);
maxn=;
maxm=maxn*;
var map:array[..,..] of longint;
cl:array[..maxn] of longint;
eg:array[..maxm] of arr;
last:array[..maxn] of longint;
l,r,f:array[..maxn] of longint;
pd:array[..maxn] of boolean;
i,j,m,n,num,sum,x:longint;
ch:char;
procedure dfs(i,j,w:longint);
var k,x,y:longint;
begin
cl[map[i,j]]:=w;
for k:= to do
begin
x:=i+dx[k]; y:=j+dy[k];
if (map[x,y]>) and (cl[map[x,y]]=) then
dfs(x,y,-w);
end;
end;
procedure add(u,v:longint);
begin
inc(sum);
eg[sum].u:=u;
eg[sum].v:=v;
eg[sum].next:=last[u];
last[u]:=sum;
end;
procedure put(i,j:longint);
var k,x,y:longint;
begin
for k:= to do
begin
x:=i+dx[k]; y:=j+dy[k];
if (map[x,y]>) then add(map[i,j],map[x,y]);
end;
end;
function Hungarian(u:longint):boolean;
var i,v:longint;
begin
i:=last[u];
while i<> do
begin
v:=eg[i].v;
if not pd[v] then
begin
pd[v]:=true;
if (l[v]=) or Hungarian(l[v]) then
begin
r[u]:=v;
l[v]:=u;
exit(true);
end;
end;
i:=eg[i].next;
end;
exit(false);
end;
procedure dfsl(u:longint);
var i,v:longint;
begin
f[u]:=;
i:=last[u];
while i<> do
begin
v:=eg[i].v;
if f[v]= then
begin
f[v]:=;
if f[l[v]]= then dfsl(l[v]);
end;
i:=eg[i].next;
end;
end; procedure dfsr(u:longint);
var i,v:longint;
begin
f[u]:=;
i:=last[u];
while i<> do
begin
v:=eg[i].v;
if f[v]= then
begin
f[v]:=;
if f[r[v]]= then dfsr(r[v]);
end;
i:=eg[i].next;
end;
end;
begin
readln(m,n);
num:=; sum:=;
for i:= to m do
begin
for j:= to n do
begin
read(ch);
if ch='.' then
begin
map[i,j]:=(i-)*n+j;
inc(num);
end
else map[i,j]:=-;
end;
readln;
end;
for i:= to m do
for j:= to n do
if (map[i,j]>) and (cl[map[i,j]]=) then
dfs(i,j,);
for i:= to m do
for j:= to n do
if map[i,j]> then put(i,j); fillchar(l,sizeof(l),);
fillchar(r,sizeof(r),);
sum:=;
for i:= to m*n do
if cl[i]= then
begin
fillchar(pd,sizeof(pd),false);
if Hungarian(i) then inc(sum);
end;
if sum*=num then
begin
writeln('LOSE');
halt;
end;
writeln('WIN');
fillchar(f,sizeof(f),);
for i:= to m*n do
if (cl[i]>) and (f[i]=) and (l[i]=) and (r[i]=) then
if cl[i]= then dfsl(i) else dfsr(i);
for i:= to m do
for j:= to n do
begin
x:=(i-)*m+j;
if f[x]= then writeln(i,' ',j);
end;
end.
ps：好像没有LOSE的点 ←_ ←