bzoj1443 [JSOI2009]游戏Game

Description

Input

输入数据首先输入两个整数N,M，表示了迷宫的边长。接下来N行，每行M个字符，描述了迷宫。

Output

若小AA能够赢得游戏，则输出一行"WIN"，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出每行一个,否则输出一行"LOSE"（不包含引号）。

Sample Input

3 3
.##
...
#.#

Sample Output

WIN
2 3
3 2

HINT

对于100%的数据，有1≤n,m≤100。对于30%的数据，有1≤n,m≤5。

正解：二分图+博弈论。

首先我们可以把这个网格图黑白染色，相邻点连边，变成二分图。

小$AA$是后手，后手要赢的充要条件是起点不一定要在最大匹配中。

如果起点不在最大匹配中，那么和起点相邻的点肯定在最大匹配中。

小$YY$移动以后，小$AA$总能移动到当前点的匹配点，所以小$AA$必胜。

判断一个点是否一定在最大匹配中可以把这个点删掉，再看最大匹配是否变化。

但是在这里如果这样做的话就会$T$，所以我们考虑别的方法。

我们先求一遍最大匹配，然后找到没有匹配的点，它肯定是合法起点。

从这个点开始搜索，直接找相邻点的匹配点，那么这个匹配点肯定也是合法点。

然后一直搜索就能找到所有可行解了。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define pos(x,y) ((x-1)*m+(y))
 6 #define N (100005)
 7 
 8 using namespace std;
 9 
10 struct edge{ int nt,to; }g[N];
11 
12 const int d1[4]={1,0,-1,0};
13 const int d2[4]={0,1,0,-1};
14 
15 int head[N],can[N],vis[N],lk[N],mp[105][105],ok,n,m,num,cnt,ans;
16 
17 il int gi(){
18   RG int x=0,q=1; RG char ch=getchar();
19   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
20   if (ch=='-') q=-1,ch=getchar();
21   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
22   return q*x;
23 }
24 
25 il char gc(){
26   RG char ch=getchar();
27   while (ch!='.' && ch!='#') ch=getchar(); return ch;
28 }
29 
30 il void insert(RG int from,RG int to){
31   g[++num]=(edge){head[from],to},head[from]=num; return;
32 }
33 
34 il int dfs(RG int x){
35   vis[x]=cnt;
36   for (RG int i=head[x],v;i;i=g[i].nt){
37     v=g[i].to; if (vis[v]==cnt) continue; vis[v]=cnt;
38     if (!lk[v] || dfs(lk[v])){ lk[x]=v,lk[v]=x; return 1; }
39   }
40   return 0;
41 }
42 
43 il void find(RG int x){
44   if (vis[x]==cnt) return; vis[x]=cnt,can[x]=1;
45   for (RG int i=head[x];i;i=g[i].nt)
46     if (vis[lk[g[i].to]]!=cnt) find(lk[g[i].to]);
47   return;
48 }
49 
50 int main(){
51 #ifndef ONLINE_JUDGE
52   freopen("game.in","r",stdin);
53   freopen("game.out","w",stdout);
54 #endif
55   n=gi(),m=gi();
56   for (RG int i=1;i<=n;++i)
57     for (RG int j=1;j<=m;++j) mp[i][j]=gc()=='.';
58   for (RG int i=1;i<=n;++i)
59     for (RG int j=1;j<=m;++j){
60       if (!mp[i][j]) continue;
61       for (RG int k=0,x,y;k<2;++k){
62     x=i+d1[k],y=j+d2[k]; if (x>n || y>m || !mp[x][y]) continue;
63     insert(pos(i,j),pos(x,y)),insert(pos(x,y),pos(i,j));
64       }
65     }
66   for (RG int i=1;i<=n;++i)
67     for (RG int j=1;j<=m;++j)
68       if (mp[i][j] && !lk[pos(i,j)]) ++cnt,dfs(pos(i,j));
69   for (RG int i=1,x,y;i<=n*m;++i){
70     x=(i-1)/m+1,y=(i-1)%m+1;
71     if (mp[x][y] && !lk[i]) ++cnt,find(i);
72   }
73   for (RG int i=1,x,y;i<=n*m;++i){
74     if (!can[i]) continue;
75     x=(i-1)/m+1,y=(i-1)%m+1;
76     if (!ok) ok=1,puts("WIN");
77     printf("%d %d
",x,y);
78   }
79   if (!ok) puts("LOSE"); return 0;
80 }