2022牛客多校（六）M. Z-Game on grid

一道博弈论题目

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

Alice and Bob are playing a game on an n×mn\times mn×m grid where each cell has either 'A', 'B' or '.' written on it. They take turns moving a chess piece on the grid and Alice moves first.

Initially the piece is on cell (1,1)(1,1)(1,1). In each player's turn, he or she can move the piece one cell right or one cell down. That is, if the piece is on cell (x,y)(x,y)(x,y) before the turn, the player can move it to (x+1,y)(x+1,y)(x+1,y) or (x,y+1)(x,y+1)(x,y+1), as long as it doesn't go beyond the grid.

At any time, if the piece is on a cell with 'A', Alice wins and the game ends. If the piece is on a cell with 'B', Bob wins and the game ends. If the piece reaches cell (n,m)(n,m)(n,m) without the game ending, then it is a draw.

Since Alice cannot decide what acts Bob will take, she would like to know if she can be in control of the situation. Given the grid they're playing on, can you tell her if she can always find a way to win, draw or lose the game no matter what acts Bob takes?

输入描述:

In the first line an integer T (1≤T≤50)T\space (1 \le T \le 50)T (1≤T≤50), representing the number of test cases.

For each test case, the first line contains two integers N,M (1≤N,M≤500)N,M\space (1\le N,M \le 500)N,M (1≤N,M≤500), representing the grid's size.

Each of the next NNN lines for the case contains MMM characters (either 'A', 'B' or '.'), describing the grid.

输出描述:

For each test case, output three words 'yes' or 'no' in one line, representing if Alice can find a way to win, draw or lose the game respectively (without quotes).

示例1

输入

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

输出

no no yes
no yes no

下面这是官方题解（有少许表述不严谨的地方，无伤大雅，结合代码来看）

代码（直接拿标准题解的，但是加了一些帮助理解的注释）如下：

#include<bits/stdc++.h>
#define M 505
using namespace std;
char str[M][M];
int n,m;
char dp[M][M];
//总的来看这个问题还是要写dfs好写 
int dfs(int x,int y,int f){
    if(str[x][y]=='A')return 1;//遇到字母了就是要停止的了，如要赢的就是到此处可以找到1了，若是要输或者平局则是遇到0了它后面的路子不能搞了 
    if(str[x][y]=='B')return 4;
    if(x==n&&y==m)return dp[x][y]=2;//能走到这里的就说明存在不经过字母的一条路径（还不一定就能保证平局）（上面先判断字母，再判断是否n,m） 
    //平局情况比较特殊，它要求走到最后（赢或输是遇到字母即可），因此任何途中的（不与右下角相邻的）'.'都不能确定为1，因此要走到最后位置再回溯确定各个'.'从而确定先手是否可以到达平局 
	char &t=dp[x][y];//注意这里是引用，数组可以实现记忆化搜索，本来dp数组是两层的，但是其实先手只用到f=0的，后手只用到f=1的，所以没必要双层 
    if(t==-1){
        if(f==0){//0表先手，先手只需或 
            t=0;
            if(x+1<=n)t|=dfs(x+1,y,f^1);//搞两层就是为了区分先后手！！！ 
            if(y+1<=m)t|=dfs(x,y+1,f^1);
        }else{//后手则和后面与，对于正常情况，就是x<n&&y<m的明显合理，对于处于边上的也是，对于x==n&&y==m的情况则已经在上面就判断了 
            t=7;
            if(x+1<=n)t&=dfs(x+1,y,f^1);
            if(y+1<=m)t&=dfs(x,y+1,f^1);
        }
    }
    return t;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%s",str[i]+1);
    memset(dp,-1,sizeof(dp));
    int t=dfs(1,1,0);
    printf("%s", t&1?"yes":"no");
    printf(" %s",t&2?"yes":"no");
    printf(" %s\n",t&4?"yes":"no");
}
int main(){
    int T;
    cin>>T;
    while(T--) solve(); 
    return 0;
}