2022 Niu Ke Duo School Six M-Z-Game on grid (dynamic programming)

Title:

Sample input:

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

Sample output:

no no yesno yes no

Title: Two people𝑁∗𝑀 N∗M takes turns to move a piece on the grid.The initial position of the pawn is (1,1) (1,1) , can only move one square in the positive direction of one dimension at a time.There are some special points on the grid, move to the point marked 'A' to win first, move to the point marked 'B' to lose first, if not moved to the special point and can no longer move the piece, it is a draw.Ask if the first mover has a win, draw, or lose strategy.

Analysis: This is a dynamic programming problem, supposef[i][j][0/1/2]=true/false means from (i,j) to (n,m) Alice (yes/no) (win/tie/loss) scheme, since the transfer methods of the three schemes are the same, I will use the winning state to deduce the dynamic equation.Wefrom position (i,j) we can only go to (i+1,j) and (i,j+1) two grids.Seeing this state representation, you can also roughly think that our dynamic transition equation is reversed, that is, recursive from back to front, so when we update to position (i, j), position (i+1, j)and the status of position (i,j+1) has been updated, thenIf it is the turn to go to position (i,j)Alice operates, that is, the case where (i+j) is an even number, because Alice's operation is under our control, so as long as there is a certain position between position (i+1,j) and position (i,j+1), Alice can win, so that meansf[i][j][0]=f[i+1][j][0]|f[i][j+1][0], of courseEnsure that position (i+1,j) and position (i,j+1) are legal, that is to say i+1<=n,j+1<=m, then if you go to position (i,j)It's Bob's turn to operate. Since Bob's operation is uncontrollable, we only have to guarantee the position (i+1, j) and position (i,j+1) are all must-win states so that we can guarantee that the result we want will happen, that is to say f[i][j][0]=f[i+1][j][0]&f[i][j+1][0], also need to ensure that the location is legal.We can also analyze the situation of draw and inevitable defeat according to the above analysis ideas, so I won't go into details here. See the code for details:

#include#include#include#include#include