2022牛客多校六 M-Z-Game on grid（动态规划）

题目：

样例输入： 

2
3 3
..B
..B
BB.
1 3
...

样例输出：

no no yes
no yes no

题意：两个人在 𝑁∗𝑀  N∗M 的网格上轮流移动一个棋子。棋子初始位为 (1,1)  (1,1) ，每次只能向某一维的正方向移动一格。网格上有一些特殊点，移到标 ’A’ 的点先手胜，移到标 ‘B’ 的点先手败，没有移到特殊点且不能再移动棋子则为平局。问先手是否有必胜、必平局、必败的策略。

分析：这是一道动态规划的题目，设f[i][j][0/1/2]=true/false表示从(i,j)走到(n,m)Alice(有/无)(必胜/平局/必败)方案，由于三种方案转移方法是相同的，我接下来就拿必胜状态来进行动态方程的推导。我们从位置(i,j)只能走到(i+1,j)和(i,j+1)两个格子其中的一个。看到这个状态表示也能大概想到我们的动态转移方程是逆着进行的，也就是从后往前递推，所以当我们更新到位置(i,j)时，位置(i+1,j)和位置(i,j+1)的状态就已经被更新好了，那么假如走到位置(i,j)时轮到Alice操作了,也就是（i+j）是偶数的情况，由于Alice的操作是我们可控的，所以只要位置(i+1,j)和位置(i,j+1)有一个位置是必胜态，那么Alice就能获胜，所以也就是说f[i][j][0]=f[i+1][j][0]|f[i][j+1][0],当然要保证位置(i+1,j)和位置(i,j+1)是合法的，也就是说i+1<=n,j+1<=m，那么假如走到位置(i,j)时轮到Bob操作了，由于Bob的操作是不可控的，所以我们只有同时保证位置(i+1,j)和位置(i,j+1)都是必胜态我们才能保证我们想要的结果发生，也就是说f[i][j][0]=f[i+1][j][0]&f[i][j+1][0]，同样的也需要保证位置是合法的。我们按照上面的分析思路同样可以分析平局和必败的情况，这里就不赘述了，细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=5e2+10;
char s[N][N];
bool f[N][N][3];//f[i][j][0/1/2]=true/false表示从(i,j)走到(n,m)Alice有/无必胜/平局/必败方案 
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%s",s[i]+1);
			for(int j=1;j<=m;j++)
			for(int k=0;k<3;k++)
				f[i][j][k]=false;
		}
		for(int i=n;i>=1;i--)
		for(int j=m;j>=1;j--)
		{
			if(s[i][j]=='A') f[i][j][0]=true;
			else if(s[i][j]=='B') f[i][j][2]=true;
			else//s[i][j]=='.'
			{
				if(i==n&&j==m)
				{
					f[i][j][1]=true;//特判不能走的情况 
					continue;
				}
				if((i+j)&1)//轮到Bob走
				{
					for(int k=0;k<3;k++)
						f[i][j][k]=true;
					if(i+1<=n)
						for(int k=0;k<3;k++)
							f[i][j][k]&=f[i+1][j][k];
					if(j+1<=m)
						for(int k=0;k<3;k++)
							f[i][j][k]&=f[i][j+1][k];
				}
				else//轮到Alice走
				{
					if(i+1<=n)
						for(int k=0;k<3;k++)
							f[i][j][k]|=f[i+1][j][k];
					if(j+1<=m)
						for(int k=0;k<3;k++)
							f[i][j][k]|=f[i][j+1][k];
				} 
			}
		}
		if(f[1][1][0]) printf("yes ");
		else printf("no ");
		if(f[1][1][1]) printf("yes ");
		else printf("no ");
		if(f[1][1][2]) puts("yes");
		else puts("no");
	}
	return 0;
}