C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 1768K, 提交时间: 2022-08-19 18:59:08

#include<bits/stdc++.h>
using namespace std;

// 并且起点不被障碍围起来k 为奇数--> niuniu赢
// k 为偶数
int n, m, k;
char g[55][55];
int dp[55][55][110];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int dfs(int x, int y, int k) // 当前在(x, y) 
{
    if(~dp[x][y][k]) return dp[x][y][k];
    if(g[x][y] == 'E' || k <= 0) return dp[x][y][k] = 0;
    for(int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 1 || b < 1 || a > n || b > m || g[a][b] == '#') continue;
        if(!dfs(a, b, k - 1)) return dp[x][y][k] = 1;
    }
    return dp[x][y][k] = 0;
}
signed main()
{
    cin >> n >> m >> k;
    memset(dp, -1, sizeof dp);
    for(int i = 1; i <= n; i ++ ) cin >> g[i] + 1;
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )if(g[i][j] == 'T')
        {
            if(dfs(i, j, k) == 1) cout << "niuniu\n";
            else cout << "niumei\n";
            return 0;
        }
}

C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 1616K, 提交时间: 2019-09-19 18:14:20

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
int r,c,k,sx,sy,sg[55][55][105];
char s[55][55];
int main(){
    cin>>r>>c>>k;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>s[i][j];
            if(s[i][j]=='T') sx=i,sy=j;
        }
    }
    for(int o=1;o<=k;o++){
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                if(s[i][j]=='#'||s[i][j]=='E') continue;
                for(int d=0;d<4;d++){
                    int ni=i+dx[d],nj=j+dy[d];
                    if(ni<1||ni>r||nj<1||nj>c||s[ni][nj]=='#') continue;
                    if(!sg[ni][nj][o-1]) sg[i][j][o]=1;
                }
            }
        }
    }
    if(sg[sx][sy][k]) cout<<"niuniu"<<endl;
    else cout<<"niumei"<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 884K, 提交时间: 2020-10-15 19:37:28

#include<iostream>
using namespace std;
int r,c,k;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char boa[51][51];
bool dp[51][51][101];
bool vis[51][51][101];
bool win(int cx,int cy,int k)
{
    if(cx<0||cx>=r||cy<0||cy>=c||boa[cx][cy]=='#')return 1;
    if(k==0)return 0;
    if(boa[cx][cy]=='E')return 0;
    if(vis[cx][cy][k])return dp[cx][cy][k];
    bool flag=0;
    for(int i=0;i<4;i++) flag|=!win(cx+dx[i],cy+dy[i],k-1);
    vis[cx][cy][k]=1;
    return dp[cx][cy][k]=flag;
}
int main()
{
    cin>>r>>c>>k;
    int x,y;
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
        { 
            cin>>boa[i][j];
            if(boa[i][j]=='T')x=i,y=j;
        }
    if(win(x,y,k))
        cout<<"niuniu\n";
    else cout<<"niumei";
    return  0;
}