[省选联考 2023] 过河卒

题目背景

棋盘上有一个过河卒，需要走到底线。卒行走的规则是可以向左移动一格，向右移动一格或者向前移动一格。同时在棋盘上有两个另一方的棋子，需要拦截这个卒走到底线。这两个棋子的走法和帅一致，可以走到前后左右四个方向上相邻的格子。因此本题可以称为“帅拦过河卒”。

题目描述

有一个 \(n\) 行 \(m\) 列的棋盘。我们用 \((i,j)\) 表示第 \(i\) 行第 \(j\) 列的位置。棋盘上有一些 障碍，还有一个黑棋子和两个红棋子。

游戏的规则是这样的: 红方先走，黑方后走，双方轮流走棋。红方每次可以选择一个红棋子，向棋盘的相邻一格走一步。具体而言，假设红方选择的这个棋子位置在 \((i,j)\)，那么它可以走到 \((i-1,j),(i+1,j),(i,j-1),(i,j+1)\) 中的一个，只要这个目的地在棋盘内且没有障碍且没有红方的另一个棋子。

黑方每次可以将自己的棋子向三个方向之一移动一格。具体地，假设这个黑棋子位置在 \((i,j)\)，那么它可以走到 \((i-1,j),(i,j-1),(i,j+1)\) 这三个格子中的一个，只要这个目的地在棋盘内且没有障碍。

在一方行动之前，如果发生以下情况之一，则立即结束游戏，按照如下的规则判断胜负（列在前面的优先）：

• 黑棋子位于第一行。此时黑方胜。

• 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。

• 当前玩家不能进行任何合法操作。此时对方胜。

现在假设双方采用最优策略，不会进行不利于自己的移动。也就是说:

• 若存在必胜策略，则会选择所有必胜策略中，不论对方如何操作，本方后续获胜所需步数最大值最少的操作。
• 若不存在必胜策略，但存在不论对方如何行动，自己都不会落败的策略，则会选择任意一种不败策略。
• 若不存在不败策略，则会选择在所有策略中，不论对方如何操作，对方后续获胜所需步数最小值最大的操作。

如果在 \(100^{100^{100}}\) 个回合之后仍不能分出胜负，则认为游戏平局。请求出游戏结束时双方一共移动了多少步，或者判断游戏平局。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 \(\text{id},T\)，分别表示测试点编号和数据组数。特别地，样例的 \(\text{id}\) 为 \(0\)。

接下来包含 \(T\) 组数据，每组数据的格式如下：

第一行包含两个正整数 \(n,m\)，表示棋盘的行数和列数。

接下来 \(n\) 行，每行包含一个长度为 \(m\) 的字符串，其中第 \(i\) 行的第 \(j\) 个字符表示棋盘上 \((i,j)\) 这个位置的状态。

在这些字符中：\(\texttt{'.'}\) 表示空位；\(\texttt{'\#'}\) 表示障碍物；\(\texttt{'X'}\) 表示黑棋；\(\texttt{'O'}\) 表示红棋。

保证黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一行。

输出格式

对于每组数据，输出一行字符串。

如果游戏平局，请输出一行 \(\texttt{"Tie"}\)。

如果红方胜，请输出一行 \(\texttt{"Red t"}\)。其中 \(\texttt{t}\) 为游戏结束时双方移动的步数之和。显然这应该是一个奇数。

如果黑方胜，请输出一行 \(\texttt{"Black t"}\)。其中 \(\texttt{t}\) 为游戏结束时双方移动的步数之和。显然这应该是一个偶数。

注意，请输出双引号内的字符串，不包含双引号。

样例 #1

样例输入 #1

0 5
4 5
...#O
.#..#
#O#..
.#..X
3 3
#.#
O.O
.X.
3 3
O..
.#X
.O.
5 5
.....
.....
..O..
#..#.
O#.X.
9 9
...######
.#.......
.#######.
.#.#.....
.#O#.####
.#.#.....
.#######.
.#X......
.O.......

样例输出 #1

Black 0
Black 2
Black 2
Tie
Red 75

样例 #2

样例输入 #2

见附件中的 zu/zu2.in

样例输出 #2

见附件中的 zu/zu2.ans

提示

【样例 1 解释】

第一组数据，红方第一步没有可行的移动，所以黑方胜。

第二组数据，无论第一步红方怎么移动，黑方都可以在下一步让黑棋子与红棋子在同一个位置。

第三组数据，无论第一步红方怎么移动，黑方都可以将自己的棋子往上移动一枚来达成胜利。

第四组数据，有一个红棋子不能动。另一个红棋子可以在第三行移动来防止黑棋子进入第一行。黑棋子也可以一直在第五行移动。如果红棋子到达第五行，黑棋子可以选择从另一边逃走。

第五组数据，在最后一行的那个红棋子可以从左边绕一圈抓住黑棋子。注意另一个红棋子可以移动。

【样例 2 解释】

这个样例中的每一组数据都满足测试点 \(5\) 到 \(13\) 中某一个测试点的限制。

【子任务】

对于所有的数据，保证：\(1 \leq T \leq 10 ; 2 \leq n \leq 10 ; 1 \leq m \leq 10 ; \text{id}\) 等于测试点编号。

对于每组数据保证：棋盘上的黑棋恰好有一个，红棋恰好有两个，且黑棋不在第一 行。

• 测试点 \(1 \sim 4\)：保证要么平局，要么红方在开始时无法移动。

• 测试点 \(5 \sim 6\)：保证 \(n \geq 4\) 。保证棋盘上第 \(n-1\) 行的每一个格子都是障碍物，且 棋盘上其他行没有障碍物。保证黑棋在前 \(n-2\) 行，有一个红棋在前 \(n-2\) 行，另一个红棋在第 \(n\) 行。

• 测试点 \(7 \sim 9\)：保证 \(m=1\)。

• 测试点 \(10 \sim 13\)：保证要么平局，要么存在策略可以在 \(9\) 步之内结束游戏。

• 测试点 \(14 \sim 20\)：无特殊限制。

范围这么小，随便设dp状态了。
定义 \(dp_{x1,y1,x2,y2,x3,y3,0/1}\) 表示现在红棋在点 \((x1,y1)\)，黑棋分别在 \((x2,y2)\) 和 \((x3,y3)\)，现在是 Alice/Bob，是谁胜。

会发现这个dp转移有环，考虑使用bfs的方式转移。

但是从初始状态进行bfs，其实很难处理。所以考虑从最终状态（也就是确定了是谁赢的状态）转移回来。把所有已经确定的状态入队。然后对于一个红方的棋子，如果他能到达的状态有红方必胜的状态，那肯定是红方必胜。不然如果全部状态是黑方必胜，那么这个点才是黑方必胜。

没有搜到的点呢？自然是平局了。
警示：两个红色棋子在同一位置上也是不合法状态

#include<bits/stdc++.h>
using namespace std;
const int N=11,INF=2e9,dx[]={0,-1,0,1},dy[]={-1,0,1,0};
int t,dp[N][N][N][N][N][N][2],ct[N][N][N][N][N][N][2],f[N][N][N][N][N][N][2],l,r,n,hjh,m,mp[N][N],nww,nw,pp,mx,mn,tfl,ax,ay,bx,by,cx,cy,fl;//f:0:平局 1:黑 2:红  dp:0:黑 1:红 
char str[N];
struct node{
	int ax,ay,bx,by,cx,cy,t;
}q[N*N*N*N*N*N*2];
inline int ok(int ax,int ay,int bx,int by,int cx,int cy)
{
	return ax&&ax<=n&&bx&&bx<=n&&cx&&cx<=n&&ay&&ay<=m&&by&&by<=m&&cy&&cy<=m&&(bx^cx||by^cy)&&!mp[ax][ay]&&!mp[bx][by]&&!mp[cx][cy];
}
void trd(int ax,int ay,int bx,int by,int cx,int cy,int t)
{
	if(ok(ax,ay,bx,by,cx,cy)&&!f[ax][ay][bx][by][cx][cy][t])
	{
		if(nw==t+1)
		{
			dp[ax][ay][bx][by][cx][cy][t]=hjh+1;
			f[ax][ay][bx][by][cx][cy][t]=t+1;
			q[++r]=(node){ax,ay,bx,by,cx,cy,t};
			return;
		}
		--ct[ax][ay][bx][by][cx][cy][t];
		if(!ct[ax][ay][bx][by][cx][cy][t])
		{
			f[ax][ay][bx][by][cx][cy][t]=(!t)+1;
			dp[ax][ay][bx][by][cx][cy][t]=hjh+1;
			q[++r]=(node){ax,ay,bx,by,cx,cy,t};
		}
	}
}
void bfs()
{
	l=1,r=0;
	for(int ax=1;ax<=n;ax++){
	for(int ay=1;ay<=m;ay++){
	for(int bx=1;bx<=n;bx++){
	for(int by=1;by<=m;by++){
	for(int cx=1;cx<=n;cx++){
	for(int cy=1;cy<=m;cy++){
		if(!ok(ax,ay,bx,by,cx,cy))
			continue;
		if(f[ax][ay][bx][by][cx][cy][0])
		{
			q[++r]=(node){ax,ay,bx,by,cx,cy,0};
			dp[ax][ay][bx][by][cx][cy][0]=dp[ax][ay][cx][cy][bx][by][0]=0;
		}
		if(f[ax][ay][bx][by][cx][cy][1])
		{
			q[++r]=(node){ax,ay,bx,by,cx,cy,1};
			dp[ax][ay][bx][by][cx][cy][1]=dp[ax][ay][cx][cy][bx][by][1]=0;
		}
	}}}}}}
	while(l<=r)
	{
		int ax=q[l].ax,ay=q[l].ay,bx=q[l].bx,by=q[l].by,cx=q[l].cx,cy=q[l].cy,t=q[l].t;
		nw=f[ax][ay][bx][by][cx][cy][t];
		hjh=dp[ax][ay][bx][by][cx][cy][t];
		if(ax==::ax&&ay==::ay&&bx==::bx&&by==::by&&cx==::cx&&cy==::cy&&t)
			break; 
		++l;
		if(!t)
		{
			trd(ax,ay,bx+1,by,cx,cy,1);
			trd(ax,ay,bx-1,by,cx,cy,1);
			trd(ax,ay,bx,by+1,cx,cy,1);
			trd(ax,ay,bx,by-1,cx,cy,1);
			trd(ax,ay,bx,by,cx+1,cy,1);
			trd(ax,ay,bx,by,cx-1,cy,1);
			trd(ax,ay,bx,by,cx,cy+1,1);
			trd(ax,ay,bx,by,cx,cy-1,1);
		}
		else
		{
			trd(ax+1,ay,bx,by,cx,cy,0);
			trd(ax,ay+1,bx,by,cx,cy,0);
			trd(ax,ay-1,bx,by,cx,cy,0);
		}
	}
}
int main()
{
// 	freopen("zu.in","r",stdin);
// 	freopen("zu.out","w",stdout);
	scanf("%*d%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		bx=by=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%s",str+1);
			for(int j=1;j<=m;j++)
			{
				if(str[j]=='#')
					mp[i][j]=1;
				else
					mp[i][j]=0;
				if(str[j]=='X')
					ax=i,ay=j;
				if(str[j]=='O')
				{
					if(bx)
						cx=i,cy=j;
					else
						bx=i,by=j;
				}
			}
		}
		memset(f,0,sizeof(f));
		memset(ct,0,sizeof(ct)); 
		for(int ax=1;ax<=n;ax++)
		{
			for(int ay=1;ay<=m;ay++)
			{
				for(int bx=1;bx<=n;bx++)
				{
					for(int by=1;by<=m;by++)
					{
						for(int cx=1;cx<=n;cx++)
						{
							for(int cy=1;cy<=m;cy++)
							{
								if(!ok(ax,ay,bx,by,cx,cy))
									continue;
								if(ax==1)
									f[ax][ay][bx][by][cx][cy][1]=f[ax][ay][bx][by][cx][cy][0]=1;
								else if(ax==bx&&ay==by||ax==cx&&ay==cy)
								{
									f[ax][ay][bx][by][cx][cy][1]=1;
									f[ax][ay][bx][by][cx][cy][0]=2;
								}
								else
								{
									int p=0;
									for(int i=0;i<4;i++)
										ct[ax][ay][bx][by][cx][cy][1]+=ok(ax,ay,bx+dx[i],by+dy[i],cx,cy)+ok(ax,ay,bx,by,cx+dx[i],cy+dy[i]);
									if(!ct[ax][ay][bx][by][cx][cy][1])
										f[ax][ay][bx][by][cx][cy][1]=1;
									ct[ax][ay][bx][by][cx][cy][0]=ok(ax-1,ay,bx,by,cx,cy)+ok(ax,ay+1,bx,by,cx,cy)+ok(ax,ay-1,bx,by,cx,cy);
									if(!ct[ax][ay][bx][by][cx][cy][0])
									f[ax][ay][bx][by][cx][cy][0]=2;
								}
							}
						}
					}
				}
			}
		}
		bfs();
		int nw=f[ax][ay][bx][by][cx][cy][1];
		if(!nw)
			puts("Tie");
		else 
		{
			if(nw==1)
				printf("Black ");
			else
				printf("Red ");
			printf("%d\n",dp[ax][ay][bx][by][cx][cy][1]);
		}
	}
}
···