题解 | #棋盘的必胜策略#

如果不是多个起点，那么我想应该讨论起点到终点的最短路径，根据它们的奇偶再联合k的奇偶及大小来判断谁能获胜；但是现在起点有多个，那么怎么办呢？

设 $dp[i][j][k]$ 表示在坐标 $(i,j)$ 当前还有 $k$ 步，轮到牛牛走路的胜负情况，如果胜，值为1；如果败，值为0，那么一个显然的递推关系就是 $dp[i\pm 1][j\pm 1][k-1]=0$ 能够推出 $dp[i][j][k]=1$ ，因为一个必败点的下一个状态一定是必胜点
接下来判断 $dp[i][j][k]=0$ 的情况，显然如果当前是终点，那么牛牛失败，或者当前 $k=0$ ，同样牛牛失败，如果当前无法移动，依然是牛牛失败，所以就这三种情况

#include <iostream>
#include <cstring>
using namespace std;
char mp[60][60];
int dp[60][60][200];
int r, c;
int ans = 0x3f3f3f3f;
int xx[] = {1, 0, -1, 0};
int yy[] = {0, 1, 0, -1};
bool dfs(int x, int y, int k){
    if(k <= 0 || mp[x][y] == 'E'){
        return dp[x][y][k] = 0;
    }
    if(dp[x][y][k] != -1) return dp[x][y][k];
    for(int i=0;i<4;i++){
        int dx = x + xx[i];
        int dy = y + yy[i];
        if(dx > r || dy > c || dx < 1 || dy < 1 || mp[dx][dy] == '#') continue;
        if(!dfs(dx, dy, k - 1)){
            return dp[x][y][k] = 1;
        }
    }
    return dp[x][y][k] = 0;
}
int main(){
    int k;
    cin >> r >> c >> k;
    int a, b;
    a = b = -1;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >> mp[i][j];
            if(mp[i][j] == 'T'){
                a = i;
                b = j;
            }
        }
    }
    memset(dp, -1, sizeof dp);
    if(dfs(a, b, k) == 1){
        puts("niuniu");
    }else{
        puts("niumei");
    }
    return 0;
}