题解
对于75分来说，操作肯定不会成环，可以暴搜
看成空格在移动，空格移动到原来的位置肯定经历了偶数个格子，但是操作的人是两个不同的人，所以肯定不会成环
对于满分做法，要找到一种更好的方式判先手是否会胜
我们看成空格在移动，每次空格必然是走一个黑棋，走一个白棋，这显然是一条交错路，我们考虑二分图
把先手看成白色，后手看成黑色，因为空格可以移动到先手所在的位置，所以空格看成黑色
在每个相邻的黑白格子之间连一条边
我们就相当于在这条路上找一条路，起点是空格，使得经过的的边数是奇数，后手每个决策的点都只能走出偶数条边
我们考虑最大匹配
如果一个点不一定在最大匹配上
那么这个点一定会顺着匹配边走出一条偶数条边的交错路（这时候这偶数条边在匹配内的状态全部取反，这个点就不在最大匹配内了）
如果一个点一定在最大匹配上
那么这个点一定不会走出一条偶数条边的交错路
如果一个点不一定在最大匹配上，那么这个点的相邻点一定在最大匹配上
如果这两个点都不在某个最大匹配上，那么这两个点可以匹配
如果这个点在某个最大匹配上，相邻点不在匹配中，由于这个点不一定在最大匹配上，可以走出一条偶数条边的交错路，加上到相邻点的这条边，是可以增广的，就不是最大匹配了
那么我们可以发现，如果起点一定在最大匹配上，那么先手必胜，如果起点不一定在最大匹配上，它下一次移动到任意一个点都是后手必胜
所以如果空格所在的点必定在最大匹配上，先手必胜，否则，后手必胜
这就变成了跑2000次二分图匹配的题了
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#define enter putchar('
')
#define space putchar(' ')
//#define ivorysi
#define pb push_back
#define mo 974711
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define MAXN 1000005
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 - '0' + c;
c = getchar();
}
res = res * f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
int N,M,K,posx,posy;
int ans[1005],tot;
char s[45][45];
int matk[2005];
int dx[] = {0,-1,0,1},dy[] = {1,0,-1,0};
bool vis[2005];
struct node {
int to,next;
}E[8005];
int head[2005],sumE;
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
int id(int x,int y) {
return (x - 1) * M + y;
}
bool match(int x) {
for(int i = head[x] ; i ; i = E[i].next) {
int v = E[i].to;
if(!vis[v]) {
vis[v] = 1;
if(!matk[v] || match(matk[v])) {
matk[v] = x;
return true;
}
}
}
return false;
}
bool check(char c) {
memset(head,0,sizeof(head));
memset(matk,0,sizeof(matk));
sumE = 0;
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= M ; ++j) {
if(s[i][j] == c) {
for(int k = 0 ; k < 4 ; ++k) {
int tx = i + dx[k],ty = j + dy[k];
if(tx < 1 || tx > N || ty < 1 || ty > M) continue;
if(s[tx][ty] != c) {
add(id(i,j),id(tx,ty));
add(id(tx,ty),id(i,j));
}
}
}
}
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= M ; ++j) {
if(s[i][j] == c) {
memset(vis,0,sizeof(vis));
match(id(i,j));
}
}
}
if(!matk[id(posx,posy)]) return false;
memset(vis,0,sizeof(vis));
vis[id(posx,posy)] = 1;
if(!match(matk[id(posx,posy)])) return true;
else return false;
}
void Solve() {
read(N);read(M);
for(int i = 1 ; i <= N ; ++i) {
scanf("%s",s[i] + 1);
for(int j = 1 ; j <= M ; ++j) {
if(s[i][j] == '.') {
posx = i;posy = j;
}
}
}
read(K);
int x,y;
for(int i = 1 ; i <= K ; ++i) {
read(x);read(y);
bool flag1 = check('O');
swap(s[x][y],s[posx][posy]);
posx = x;posy = y;
bool flag2 = check('X');
if(flag1 && flag2) ans[++tot] = i;
read(x);read(y);
swap(s[x][y],s[posx][posy]);
posx = x;posy = y;
}
out(tot);enter;
for(int i = 1 ; i <= tot ; ++i) {
out(ans[i]);enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}