挺套路的博弈论，实际上就是 Game on Graph 与 Game on Graph，但是考场上多测没清空挂了。寄。
并且 
不过 ABC 那个官方题解好像给的是 \(O(m \log n)\) 的做法，放这题是过不去的啦x
首先显然三个棋子压状态大概是 \(10^6\) 级别的，多测 \(T=10\)，那么猜测是一个 \(O(Tn^6)\) 的做法。
直接暴搜索出所有的状态，然后建图出来，然后就跟上面那个题一模一样了。
具体来说，考虑博弈 DP。
- 若一个点没有出边，那么它为必败态；
- 若一个点的出边中有一个必败态，那么它为必胜态；
- 若一个点的出边中都是必胜态，那么它为必败态；
- 若一个点的出边中没有必败态，且存在平局态，那么它为平局态。
平局态实际上就是出现环的情况。考虑类似于拓扑排序的做这个东西，根据上面的规则直接跑即可。
记录最小 / 最大步数可以在拓扑的时候同时进行，具体就是给必胜态和必败态加一个优先级，这样必胜态从所有必败态的出边中找一个最小值，必败态从所有出边找一个最大值，优先计算必败态的答案即可。
关于状态数：首先根据奇偶性，每个状态作为先手还是后手是确定的，而相同的两个红棋是可以互相交换的，两个状态相同，可以压缩成一个状态。这样状态数上界为 \(5 \times 10^5\)，可以跑过去。民间数据好像不考虑相互交换也可以跑过去，官方数据不知道会怎样。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005, V = 2000000;
int T;
int n, m;
char s[14][14];
#define forGraph(u, v) for (int i = fst[u], v = to[i]; i; i = nxt[i], v = to[i])
bool vis[MAXN];
int type[MAXN]; // 0: undetermined 1: lose 2: win
struct Graph {
int fst[MAXN], nxt[8 * MAXN], to[8 * MAXN], tot;
int q1[MAXN], q2[MAXN], q1h, q1t, q2h, q2t;
int deg[MAXN];
int f[MAXN], g[MAXN];
inline void Add(int u, int v) {
add(v, u);
deg[u]++;
}
inline void clear() {
for (int i = 0; i < V; i++)
fst[i] = 0;
tot = 0;
}
inline void add(int u, int v) {
to[++tot] = v, nxt[tot] = fst[u], fst[u] = tot;
}
inline void topo() {
q1h = 0, q1t = 1;
q2h = 0, q2t = 1;
for (int i = 0; i < V; i++) if (vis[i]) {
if (!deg[i]) {
type[i] = 1, q1[++q1h] = i;
}
}
while (q1h >= q1t || q2h >= q2t) {
if (q1h >= q1t) {
int u = q1[q1t++];
forGraph(u, v) if (!type[v]) { // not determined
type[v] = 2;
f[v] = f[u] + 1;
q2[++q2h] = v;
} else if (type[v] == 2) {
f[v] = min(f[v], f[u] + 1);
}
} else {
int u = q2[q2t++];
forGraph(u, v) if (!type[v]) { // not determined
deg[v]--;
g[v] = max(g[v], f[u] + 1);
if (!deg[v]) {
type[v] = 1;
q1[++q1h] = v;
f[v] = g[v];
}
}
}
}
}
} g;
int id(int ax, int ay, int bx, int by, int cx, int cy, bool f) {
if (make_pair(bx, by) > make_pair(cx, cy)) swap(bx, cx), swap(by, cy);
return ((((((ax - 1) * 10 + ay - 1) * 10 + bx - 1) * 10 + by - 1) * 10 + cx - 1) * 10 + cy - 1) + f * 1000000;
}
const vector<pair<int, int>> ma = {{0, 1}, {0, -1}, {-1, 0}};
const vector<pair<int, int>> mb = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int dfs(int ax, int ay, int bx, int by, int cx, int cy, bool f) {
int S = id(ax, ay, bx, by, cx, cy, f);
if (vis[S]) return S;
vis[S] = 1;
if ((ax == bx && ay == by) || (ax == cx && ay == cy) || ax == 1) {
return S;
}
if (f) {
// move b
for (auto &p : mb) {
int nx = bx + p.first, ny = by + p.second;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
s[nx][ny] != '#' && !(nx == cx && ny == cy)) {
int T = dfs(ax, ay, nx, ny, cx, cy, 0);
g.Add(S, T);
}
}
// move c
for (auto &p : mb) {
int nx = cx + p.first, ny = cy + p.second;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
s[nx][ny] != '#' && !(nx == bx && ny == by)) {
int T = dfs(ax, ay, bx, by, nx, ny, 0);
g.Add(S, T);
}
}
} else {
// move a
for (auto &p : ma) {
int nx = ax + p.first, ny = ay + p.second;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
s[nx][ny] != '#') {
int T = dfs(nx, ny, bx, by, cx, cy, 1);
g.Add(S, T);
}
}
}
return S;
}
int main() {
scanf("%*d%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", s[i] + 1);
}
int ax, ay, bx = 0, by, cx, cy;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i][j] == 'X') ax = i, ay = j;
if (s[i][j] == 'O') {
if (!bx) bx = i, by = j;
else cx = i, cy = j;
}
}
}
g.clear();
for (int i = 0; i < V; i++) {
vis[i] = 0, type[i] = 0;
g.deg[i] = 0;
g.f[i] = 0;
g.g[i] = 0;
}
dfs(ax, ay, bx, by, cx, cy, 1);
g.topo();
int S = id(ax, ay, bx, by, cx, cy, 1);
if (!type[S]) {
printf("Tie\n");
continue;
}
if (type[S] == 1) {
printf("Black %d\n", g.f[S]);
} else {
printf("Red %d\n", g.f[S]);
}
}
return 0;
}