2022 Niu Ke Duo School (6) M. Z-Game on grid

A game theory topic

Link: Login—Professional IT Written TestInterview preparation platform_Niuke.com
Source: Niuke.com

Title description

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 thegrid 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 orone 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 controlof 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?

Enter description:

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.

Output description:

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).

Example 1

Enter

23 3..B..BBB.1 3...

Output

no no yesno yes no

The following is the official solution to the problem (there are some inaccurate expressions, it is harmless, combined with the code)

The code (solved directly from the standard problem, but with some comments to help understanding) is as follows:

#include#define M 505using namespace std;char str[M][M];int n,m;char dp[M][M];//In general, this problem still needs to be written in dfsint dfs(int x,int y,int f){if(str[x][y]=='A')return 1;//If you encounter a letter, you will stop. If you want to win, you can find 1 here. If you want to lose or draw, it isWhen you encounter 0, the path behind it can't be done.if(str[x][y]=='B')return 4;if(x==n&&y==m)return dp[x][y]=2;//If you can get here, it means that there is a path that does not pass through letters (it may not guarantee a draw) (the above is judged firstletters, and then determine whether n,m)//The case of a draw is special, it requires to go to the end (win or lose by encountering letters), so any '.' on the way (not adjacent to the lower right corner) cannot be determined to be 1, so it is necessary to go toThe last position is backtracked to determine each '.' to determine whether the first mover can reach a drawchar &t=dp[x][y];//Note that this is a reference. The array can realize memory search. Originally, the dp array has two layers, but in fact, only f=0 is used in the first hand, and only f is used in the second hand.=1, so there is no need for double layersif(t==-1){if(f==0){//0 means the first move, the first move only needs ort=0;if(x+1<=n)t|=dfs(x+1,y,f^1);//The purpose of doing two layers is to distinguish between the hands!!!if(y+1<=m)t|=dfs(x,y+1,f^1);}else{//The back hand and the back and, for the normal situation, it is obviously reasonable for x>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;}