1443: [JSOI2009]游戏Game

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1334 Solved: 613
[Submit][Status][Discuss]

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。

题解

黑白染色，可走的点连边，做最大匹配
发现如果先手放到非匹配点上，后手要么无路可走，失败，要么走到匹配点上；如果后手走到匹配点上，先手沿匹配点走，后手要么无路可走，要么走非匹配边，由于不存在增广路，后手走到的一定是一个匹配点。。。。一直这样走下去，发现走的是交替路，由于不存在增广路，交替路的结尾一定是匹配边，后手一定无路可走。此时先手必胜
必胜点即为所有最大匹配方案中的未匹配点
其他点均为必败点（相当于先手走必胜点后，后手不得不走的那个点，因此必败）
怎么求呢？
发现从未匹配点开始，走非匹配边、匹配边后，交换匹配边与非匹配边，匹配合法且最大匹配不变。即我们从每个非匹配点走交替路，然后所有匹配点连过来的点都是答案（即与起点同集合的点）

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <queue>#include <vector>#include <map>#include <string> #include <cmath> #include <sstream>#define min(a, b) ((a) < (b) ? (a) : (b))#define max(a, b) ((a) > (b) ? (a) : (b))#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))template<class T>inline void swap(T &a, T &b){ ???T tmp = a;a = b;b = tmp;}inline void read(int &x){ ???x = 0;char ch = getchar(), c = ch; ???while(ch < '0' || ch > '9') c = ch, ch = getchar(); ???while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); ???if(c == '-') x = -x;}const int INF = 0x3f3f3f3f;const int MAXN = 100 + 10;const int dx[4] = {0,0,1,-1};const int dy[4] = {1,-1,0,0};int n, m, hao[MAXN][MAXN], vis1[MAXN * MAXN], vis2[MAXN * MAXN], cnt1, cnt2, lk1[MAXN * MAXN], lk2[MAXN * MAXN], vis[MAXN * MAXN];char s[MAXN][MAXN];struct Edge{ ???int u,v,nxt; ???Edge(int _u, int _v, int _nxt){u = _u;v = _v;nxt = _nxt;} ???Edge(){}}edge[100000];int head[MAXN * MAXN], cnt;inline void insert(int a, int b){ ???edge[++cnt] = Edge(a,b,head[a]); ???head[a] = cnt;}int dfs(int x){ ???for(int pos = head[x];pos;pos = edge[pos].nxt) ???{ ???????int i = edge[pos].v; ???????if(vis[i]) continue; ???????vis[i] = 1; ???????if(lk2[i] == -1 || dfs(lk2[i])) ???????{ ???????????lk2[i] = x, lk1[x] = i; ???????????return 1; ???????} ???} ???return 0;} void dfs1(int x){ ???vis1[x] = 1; ???for(int pos = head[x];pos;pos = edge[pos].nxt) ???{ ???????int i = edge[pos].v; ???????if(lk2[i] == -1 || vis1[lk2[i]]) continue; ???????dfs1(lk2[i]); ???}}void dfs2(int x){ ???vis2[x] = 1; ???for(int pos = head[x];pos;pos = edge[pos].nxt) ???{ ???????int i = edge[pos].v; ???????if(lk1[i] == -1 || vis2[lk1[i]]) continue; ???????dfs2(lk1[i]); ???}}int main(){ ???read(n), read(m); ???for(int i = 1;i <= n;++ i) ???????scanf("%s", s[i] + 1); ????for(int i = 1;i <= n;++ i) ???????for(int j = 1;j <= m;++ j) ???????????if(s[i][j] == '#') continue; ???????????else if((i + j & 1)) hao[i][j] = ++ cnt1; ???????????else hao[i][j] = ++ cnt2; ???//左奇右偶 ????for(int i = 1;i <= n;++ i) ???????for(int j = 1;j <= m;++ j) ???????????if(s[i][j] == '.' && (i + j) & 1) ???????????{ ???????????????for(int k = 0;k < 4;++ k) ???????????????{ ???????????????????int x = i + dx[k], y = j + dy[k]; ???????????????????if(x <= 0 || x > n || y <= 0 || y > m || s[x][y] == '#') continue; ???????????????????insert(hao[i][j], hao[x][y]); ???????????????} ???????????} ???memset(lk1, -1, sizeof(lk1)); ???memset(lk2, -1, sizeof(lk2)); ???for(int i = 1;i <= cnt1;++ i) ????{ ???????memset(vis, 0, sizeof(vis)); ???????dfs(i); ???} ???for(int i = 1;i <= cnt1;++ i) ???????if(lk1[i] == -1) dfs1(i); ???cnt = 0;memset(head, 0, sizeof(head)); ???for(int i = 1;i <= n;++ i) ???????for(int j = 1;j <= m;++ j) ???????????if(s[i][j] == '.' && (i + j) & 1) ???????????{ ???????????????for(int k = 0;k < 4;++ k) ???????????????{ ???????????????????int x = i + dx[k], y = j + dy[k]; ???????????????????if(x <= 0 || x > n || y <= 0 || y > m || s[x][y] == '#') continue; ???????????????????insert(hao[x][y], hao[i][j]); ???????????????} ???????????} ???for(int i = 1;i <= cnt2;++ i) ???????if(lk2[i] == -1) dfs2(i); ???int flag = 0; ???for(int i = 1;i <= n;++ i) ???????for(int j = 1;j <= m;++ j) ???????????if(s[i][j] == '#') continue; ???????????else if((i + j) & 1 && vis1[hao[i][j]]) ?????????????{ ???????????????if(!flag) printf("WIN\n"), flag = 1; ???????????????printf("%d %d\n", i, j); ???????????} ???????????else if(!((i + j) & 1) && vis2[hao[i][j]]) ???????????{ ???????????????if(!flag) printf("WIN\n"), flag = 1; ???????????????printf("%d %d\n", i, j); ???????????} ???if(!flag) printf("LOSE"); ????return 0;}