暴力写法直接dfs
#include<bits/stdc++.h> using namespace std; char ff[45][45]; int nn[45][45], n, m; int ok[1005]; int xx, yy, nowx, nowy; const int dir[4][2] = { 0, -1, -1, 0, 0, 1, 1, 0 }; vector<int> ans; bool dfs(int x, int y, int z) { int dx, dy; for (int i = 0; i < 4; i++) { dx = x + dir[i][0]; dy = y + dir[i][1]; if (dx < 1 || dx > n || dy < 1 || dy > m || nn[dx][dy] != z) { continue; } swap(nn[dx][dy], nn[x][y]); if (!dfs(dx, dy, z ^ 1)) { swap(nn[dx][dy], nn[x][y]); return true; } swap(nn[dx][dy], nn[x][y]); } return false; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", ff[i] + 1); } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (ff[i][j] == 'X') { nn[i][j] = 1; } else if (ff[i][j] == 'O') { nn[i][j] = 0; } else { nn[i][j] = 2; xx = i; yy = j; } } int q; scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d %d", &nowx, &nowy); ok[i] = dfs(xx, yy, 0); swap(nn[xx][yy], nn[nowx][nowy]); xx = nowx, yy = nowy; if (ok[i] && dfs(xx, yy, 1)) { ans.push_back(i); } scanf("%d %d", &nowx, &nowy); swap(nn[xx][yy], nn[nowx][nowy]); xx = nowx, yy = nowy; } printf("%d ", ans.size()); for (auto v : ans) { printf("%d ", v); } return 0; }
首先我们可以拿一个2X2的格子证明 走过的路径不可能成环
则我们可以把图黑白染色 变成一个二分图(空的点为黑色) 如果一个点必在最大匹配中 那么它可以沿着匹配边走 最终的交错路边数一定是奇数
（因为如果是偶数的话 就说明该点可替换 不是必在最大匹配中的点）
现在问题变成了如果判断一个点是否是二分图最大匹配中的必须点 我们把这个点从图中去掉 然后跑它匹配点的增广路即可