原题链接 过河卒

题目大意

一个 \(n\times n\) 的棋盘，上有一黑二红三子和障碍物，黑棋每次可以从 \((x,y)\) 移动到 \((x-1,y),(x,y-1),(x,y+1)\)（目标点不能有障碍物），红棋每次可以从 \((x,y)\) 移动到 \((x-1,y),(x+1,y),(x,y-1),(x,y+1)\)（目标点不能有障碍物），求双方都使用最优策略的情况下谁最少要几步获胜。

某一方获胜当且仅当：

• 黑棋在操作后到达第一行，此时黑方胜。
• 双方棋子在某次操作前重叠，此时当前要行棋的一方获胜；
• 某一方在他的一轮中不能移动，另一方获胜。

\(1\le n\le 10\)

解题思路

乍一看是一道大模拟，但是确实是注意到 \(n\le 10\)，所以我们可以考虑暴力，令状态 \((x1,y1,x2,y2,x3,y3)\) 表示黑棋，两枚红棋的坐标，最多 \(10^6\) 种。

这道题是一道博弈论题，状态之间可以相互转移，形成一张图，所以可以考虑拓扑排序求出每个状态是 必胜态/必败态/平局。

具体的，如果在拓扑排序时一个状态 \(u\) 可以从 \(v\) 转移过来，有以下几种情况：

• \(u\) 为必败态，此时显然 \(v\) 为必胜态，更新 \(v\) 的状态和步数。

• \(u\) 为必胜态，此时考虑：

  • 若 \(v\) 确定为必胜态，那么不更新 \(v\)

  • 若 \(v\) 不确定/确定为必败态：

    • 如果这不是 \(v\) 被枚举过的的最后一条出边，那么不更新。（如果有环\(^\dagger\)经过 \(v\) ，且 \(v\) 必败，那么显然 \(v\) 可以向环\(^\dagger\)转移以达到平局的目的，所以只有确认了不经过环\(^\dagger\)才能更新。）
    • 否则更新 \(v\) 的状态与步数。

\(\dagger\)：此处的环指的是转移的环上没有必胜的点，此时整个环都不确定必胜或必败，即为平局。

所以可以先正向bfs以确定可达态，然后跑一遍拓扑排序来确定状态即可。

细节

1. 6维状态可以变成一个6位10制数，便于存储。
2. 记得判不合法情况（棋子超出棋盘，两个红棋重合）
3. 判断终态（黑棋到达第一行，黑棋和红棋重合）并且赋初值，为后续转移准备。
4. 需要将一些 \(\text{int}\) 换成 \(\text{short}\) 来缩短 memset 的时间，用 vector 的换成邻接表之类的。（卡常部分，实现常数小的请无视）

代码（卡常）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define il inline 

struct node{unsigned int a[6];};
const int M = 8.5e6 + 5, V = 1e7 + 5, N = 15;
char a[N][N],deg[V];
short ans[V];
int stf, n, m, mxv, fst[V], nxt[M], to[M], gst, h = 2;
bool vis[V];

il void add(int x, int y)
{
	nxt[h] = fst[x], fst[x] = h, to[h] = y, h ++;
}

il node getpos(int x)
{
	return {x / 100000 + 1, x % 100000 / 10000 + 1, x % 10000 / 1000 + 1,
        x % 1000 / 100 + 1, x % 100 / 10 + 1, x % 10 + 1};
}

il int getst(node &x)
{
	return (x.a[0] - 1) * 100000 + (x.a[1] - 1) * 10000 + (x.a[2] - 1) * 1000
        + (x.a[3] - 1) * 100 + (x.a[4] - 1) * 10 + x.a[5] - 1;
}

il bool getf(node &x)
{
	return (x.a[0] + x.a[1] + x.a[2] + x.a[3] + x.a[4] + x.a[5]) & 1;
}

il bool checkend(node &x)
{
	return ((x.a[0] == 1) || (x.a[0] == x.a[2] && x.a[1] == x.a[3]) ||
        (x.a[0] == x.a[4] && x.a[1] == x.a[5]));
}

il bool checkp(node &x)
{
	return x.a[0] && x.a[2] && x.a[4] && x.a[1] && x.a[3] && x.a[5] &&
	x.a[0] <= n && x.a[2] <= n && x.a[4] <= n &&
	x.a[1] <= m && x.a[3] <= m && x.a[5] <= m;
}

il bool check(node x)
{
	return !(x.a[2] == x.a[4] && x.a[3] == x.a[5]) &&
	!(a[x.a[0]][x.a[1]] == '#' ||a[x.a[2]][x.a[3]] == '#' ||a[x.a[4]][x.a[5]] == '#');
}

il bool check(int x){return check(getpos(x));}

const int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, 1, -1, 0};
node stt;

struct Q
{
	int a[(M >> 2)], l, r;
	Q(){l = 1, r = 0;}
	il void push(int v){a[++r] = v;}
	il int frontp(){return a[l++];}
	il bool empty(){return r + 1 == l;}
};

void init()
{
	Q q;

	vis[getst(stt)] = 1;
	q.push(getst(stt));
	while(!q.empty())
	{
		int i = q.frontp();
		node pi = getpos(i);
		if(checkend(pi))
		{
			ans[i] = -1;
			continue;
		}
		node w = pi;
		bool gw = getf(w);
		char st = gw != stf ? 0 : 2;
		char ed = gw != stf ? 2 : 6;
		for(char j = st; j < ed; j += 2)
		{
			int x = w.a[j], y = w.a[j + 1];
			node w1 = w;
			char ked = 4 - (gw != stf);
			for(char k = 0; k < ked; k ++)
			{
				w1.a[j] = x + dx[k];
				w1.a[j + 1] = y + dy[k];
				if(!checkp(w1) || !check(w1)) continue;
				deg[i] ++;
				int gw1 = getst(w1);
				if(!vis[gw1]) vis[gw1] = 1, q.push(gw1), fst[gw1] = 0;
				add(gw1, i);
			}
		}
		if(deg[i] == 0) ans[i] = -1;
	}
}

void bfs()
{
	Q q;

	init();

	for(int i = 0; i < mxv; i ++)
		if(vis[i] && !deg[i]) q.push(i);

	while(!q.empty())
	{
		int i = q.frontp();
		for(int j = fst[i]; j; j = nxt[j])
		{
			int k = to[j];
			if(!ans[k])
			{
				if(ans[i] < 0) ans[k] = -ans[i] + 1, deg[k] --, q.push(k);
				else
					if(--deg[k] == 0) ans[k] = -(ans[i] + 1), q.push(k);
			}
		}
	}
}

void solve()
{
	memset(ans, 0, sizeof ans);
	memset(deg, 0, sizeof deg);
	memset(vis, 0, sizeof vis);
	h = 2;
	
	cin >> n >> m;
    node vv = {n, m, n, m, n, m};
	mxv = getst(vv);
	stt = {};
	for(int i = 1; i <= n ; i ++)
	{
		cin >> a[i] + 1;
		for(int j = 1; j <= m; j ++)
			if(a[i][j] == 'X')
				stt.a[0] = i, stt.a[1] = j;
			else if(a[i][j] == 'O')
			{
				if(stt.a[2]) stt.a[4] = i, stt.a[5] = j;
				else stt.a[2] = i, stt.a[3] = j;
			}
	}
	stf = getf(stt);
	gst = getst(stt);
	bfs();
	
	if(ans[gst] == 0) cout << "Tie\n";
	else if(ans[gst] < 0) cout << "Black " << -ans[gst] - 1 << "\n";
	else cout << "Red " << ans[gst] - 1 << "\n";
}

signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int id, t;cin >> id >> t;while(t --) solve();

	return 0;
}