题面
题解
通过观察，我们可以发现如下性质：
- 可以看做是2个人在不断移动空格，只是2个人能移动的边不同
- 一个位置不会被重复经过 ： 根据题目要求，因为是按黑白轮流走，所以不可能重复经过一个点，不然就变成一个人连续走2次了
- 原图是一个二分图 ： 也是由按黑白轮流走这个要求得到的
因此我们对原图按照与原点的距离进行黑白染色，再跑二分图博弈即可。
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 45
#define ac 5000
int n, m, sx, sy, all;
int id[AC][AC], ans[ac], link[ac];
int a[6] = {-1, 1, 0, 0}, b[6] = {0, 0, -1, 1};
bool can[AC][AC], z[ac], vis[ac];
char s[AC][AC];
struct node{int x, y;}back[ac];
inline int read()
{
int x = 0;char c = getchar();
while(c > '9' || c < '0') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
bool check(int x, int y)//起点是黑色
{
int tmp = abs(x - sx) + abs(y - sy);
if((tmp & 1) && s[x][y] == 'O') return 1;//相距奇数格，则为白格，需要白色
else if(!(tmp & 1) && s[x][y] == 'X') return 1;
else if(s[x][y] == '.') return 1;
return 0;
}
bool dfs(int x)
{
for(R i = 0; i < 4; i ++)
{
int xx = back[x].x + a[i], yy = back[x].y + b[i], ID = id[xx][yy];
if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;
if(!can[xx][yy] || vis[ID]) continue;
vis[ID] = true;
if(!link[ID] || dfs(link[ID]))
{
link[ID] = x, link[x] = ID;
return true;
}
}
return false;
}
void cal()
{
int tmp = (sx + sy) % 2;
for(R i = 1; i <= all; i ++)
{
int x = back[i].x, y = back[i].y;
if((x + y) % 2 != tmp || !can[x][y]) continue;//和为奇数则在T集合
memset(vis, 0, sizeof(vis)), dfs(i);
}
}
bool dfs1(int x)
{
for(R i = 0; i < 4; i ++)
{
int xx = back[x].x + a[i], yy = back[x].y + b[i], ID = id[xx][yy];
if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;
if(!can[xx][yy] || vis[ID]) continue;
vis[ID] = true;
if(!link[ID] || dfs(link[ID])) return true;
}
return false;
}
void pre()
{
n = read(), m = read(), all = n * m;
int tmp1 = 1, tmp2 = 2;
for(R i = 1; i <= n; i ++)
{
scanf("%s", s[i] + 1);
for(R j = 1; j <= m; j ++)
{
if(s[i][j] == '.') sx = i, sy = j;
if((i + j) & 1) id[i][j] = tmp2, back[tmp2] = (node){i, j}, tmp2 += 2;
else id[i][j] = tmp1, back[tmp1] = (node){i, j}, tmp1 += 2;
}
}
for(R i = 1; i <= n; i ++)
for(R j = 1; j <= m; j ++) can[i][j] = check(i, j);
}
void check_()
{
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++) printf("%d ", can[i][j]);
printf("
");
}
for(R i = 1; i <= n; i ++)
{
for(R j = 1; j <= m; j ++) printf("%d ", link[id[i][j]]);
printf("
");
}
}
void work()
{
int T = read() << 1, x, y, ID, tmp; bool done;
for(R i = 0; i <= T; i ++)
{
for(R j = 1; j <= all; j ++) z[j] = 0;
if(i) x = read(), y = read(), ID = id[x][y];
else x = sx, y = sy, ID = id[x][y];
can[x][y] = 0;//这个要在一开始就修改
if(!link[ID]) continue;//搜S/T集合中有没有可到达的同侧未匹配点来取代它,因为直接搜不太方便，所以直接搜对面的匹配点是否可以找到增广路
memset(vis, 0, sizeof(vis));
done = dfs(link[ID]);//找到了说明这个点不是必须点
tmp = link[ID];//所以搜这个点的匹配点是否可以找到对面的一个未匹配点(反向增广)
if(done) link[ID] = 0;//清空这个点的匹配，因为这个点已经到过了，所以就不能到达了,如果已经匹配上了就不能改了
else if(!done) link[ID] = link[tmp] = 0, ans[i] = true;//没有可取代点就先手必胜
}
/*for(R i = 0; i <= T; i ++) printf("%d ", ans[i]);
printf("
");*/
int rnt = 0;
for(R i = 0; i <= T; i += 2)
if(ans[i] == 1 && ans[i + 1] == 1) ++ rnt;
printf("%d
", rnt);
for(R i = 0; i <= T; i += 2)
if(ans[i] == 1 && ans[i + 1] == 1) printf("%d
", (i + 2) >> 1);
}
int main()
{
// freopen("in.in", "r", stdin);
pre();
cal();
work();
// fclose(stdin);
return 0;
}