真的没想到、、、果然反应太迟钝，看到题目毫无思路，一点联想都没有。
按照网上博客的说法：一眼棋盘染色二分->二分图->最大匹配->BINGO?果然我还是太弱了……
我们将棋盘黑白染色，相邻两点之间的转移转化为图上的边。根据最大匹配的定义，如果我们最开始将棋子放在一个未匹配的点上，一定会到达一个匹配点（不然若到达了另一个未匹配点就说明还有可以扩张的匹配。）此后，因为已经是最大匹配所以不存在可以增广的交替路。所以这样先手一定会比后手多走一步，获得胜利。所以问题转化为：有哪些点不在最大匹配上？注意最大匹配的情况数是很多的。
所以我们枚举每一个点是否可以不被纳入最大匹配，若可以，说明是一个先手必胜点。
#include <bits/stdc++.h> using namespace std; #define maxn 205 int n, m, a[maxn][maxn], link[maxn * 100]; int Map[maxn * 100][5], ans[maxn * 100][2]; int cnt, tot, id[maxn][maxn]; int px[4] = { 0, 1, -1, 0 }, py[4] = { 1, 0, 0, -1 }; bool vis[maxn * 100]; char s[maxn]; int read() { int x = 0, k = 1; char c; c = getchar(); while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * k; } bool dfs(int u) { for(int i = 1; i <= Map[u][0]; i ++) { int v = Map[u][i]; if(vis[v]) continue; vis[v] = 1; if(!link[v] || dfs(link[v])) { link[v] = u, link[u] = v; return 1; } } return 0; } void add(int u, int v) { Map[u][++ Map[u][0]] = v; } int main() { n = read(), m = read(); for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) id[i][j] = ++ cnt; for(int i = 1; i <= n; i ++) { scanf("%s", s + 1); for(int j = 1; j <= n; j ++) if(s[j] == '#') a[i][j] = 1; } for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(!a[i][j] && (i + j) % 2) for(int k = 0; k <= 3; k ++) { int mx = i + px[k], my = j + py[k]; if(mx >= 1 && mx <= n && my >= 1 && my <= m && !a[mx][my]) { add(id[i][j], id[mx][my]); add(id[mx][my], id[i][j]); } } for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(!a[i][j] && (i + j) % 2) { memset(vis, 0, sizeof(vis)); if(dfs(id[i][j])) cnt ++; } for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(!a[i][j]) { memset(vis, 0, sizeof(vis)); vis[id[i][j]] = 1; if(!link[id[i][j]] || dfs(link[id[i][j]])) { ans[++ tot][0] = i, ans[tot][1] = j; link[id[i][j]] = 0; } } if(!tot) printf("LOSE"); else { printf("WIN "); for(int i = 1; i <= tot; i ++) printf("%d %d ", ans[i][0], ans[i][1]); } return 0; }