可以看做是将空格按照黑白交替的方式移动。
先把格子黑白染色，不妨令起点为黑色，相邻且颜色不同的格子连边。连边时注意，假设起点坐标为(x,y)，且(x+y)%2=0，则只有同样横纵坐标之和为奇数的黑格子才有用。

如果起点在一定最大匹配中，则一定先手必胜。因为起点一定在奇数边的交错轨中，只要每次都沿着匹配的边走，一定可以赢。

如果起点不一定在最大匹配中，则后手必胜。因为第一步走到的点，一定在不包括起点的最大匹配中。

所以只要当前点一定在最大匹配中就是必胜态，如果走之前是必胜态，走之后还是必胜态，那么说明这一步就走错了。

至于最大匹配用匈牙利算法

```cpp

#include <bits/stdc++.h>
using namespace std;![](http://)

int n, m;
int arr[45][45];
int tot;
int x, y;
int num[45][45];
vector<int> edges[10005];
bool vis[10005], ban[10005];
int mat[10050];

bool dfs(int i) {
    if (ban[i]) return false;
    for (int j = 0; j < edges[i].size(); j++) {
        int k = edges[i][j];
        if (!vis[k] && !ban[k]) {
            vis[k] = 1;
            if (!mat[k] || dfs(mat[k])) {
                mat[k] = i;
                mat[i] = k;
                return true;
            }
        }
    }
    return false;
}

int ans[10005];
int main() {
    scanf("%d %d", &n, &m);
    char str[45];
    for (int i = 1; i <= n; i++) {
        scanf("%s", str + 1);
        for (int j = 1; j <= m; j++) {
            if (str[j] == 'O') arr[i][j] = 1;
            else if (str[j] == 'X') arr[i][j] = 2;
            else arr[i][j] = 2, x = i, y = j;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (arr[i][j] == 1 ^ (((i + j) & 1) == ((x + y) & 1)))
                num[i][j] = ++tot;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!num[i][j]) continue;
            if (num[i + 1][j]) {
                edges[num[i][j]].push_back(num[i + 1][j]);
                edges[num[i + 1][j]].push_back(num[i][j]);
            }
            if (num[i][j + 1]) {
                edges[num[i][j]].push_back(num[i][j + 1]);
                edges[num[i][j + 1]].push_back(num[i][j]);
            }
        }
    }
    for (int i = 1; i <= tot; i++) {
        memset(vis, 0, sizeof(vis));
        if (!mat[i]) dfs(i);
    }
    int k;
    scanf("%d", &k);
    for (int i = 1; i <= k << 1; i++) {
        int fuck = num[x][y];
        ban[fuck] = 1;
        if (mat[fuck]) {
            int match = mat[fuck];
            mat[match] = mat[fuck] = 0;
            memset(vis, 0, sizeof(vis));
            ans[i] = (!dfs(match));
        }
        scanf("%d %d", &x, &y);
    }
    int res = 0;
    for (int i = 1; i <= k; i++)
        res += (ans[i * 2 - 1] & ans[i * 2]);
    printf("%d\n", res);
    for (int i = 1; i <= k; i++) {
        if (ans[i * 2 - 1] & ans[i * 2]) {
            printf("%d\n", i);
        }
    }
    return 0;
}

水

被坑了3次，幸亏有小号。。

沙发

地板