Newcoder 21669 牛牛VS牛妹 (博弈+思维)

链接：https://ac.nowcoder.com/acm/problem/21669

来源：牛客网

题目大意

给你一个网格，有些点被#覆盖了不能再走，其他点是空地，现在牛牛和牛妹轮流开始将空地变成#

如果当前轮到的人操作之后左上角到右下角不存在通路了，当前操作的人就输了

通路只能是从左上角到右下角往右或者往下走的路径

牛牛先开始操作，如果双方都是绝顶聪明，输出最后谁赢

保证一开始给你的网格是存在一条左上角到右下角的通路的，当然，左上角与右下角都是空地。

题目分析 

发现任意一条路径其奇偶性都是一样的，

所以不妨取最短路经长度，我们只要判断除不可走点

之外的长度与最短路径长度差的奇偶性即可。

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

#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long

#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=1e2;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
发现任意一条路径其奇偶性都是一样的，
所以不妨取最短路经长度，我们只要判断除不可走点
之外的长度与最短路径长度差的奇偶性即可。
*/

int n,m;
char s[maxn][maxn];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int vis[maxn][maxn];
void bfs(){
    queue<int> p;
    vis[0][0]=1;
    p.push(0);
    while(!p.empty()){
        int tp=p.front();p.pop();
        int tx=tp/m,ty=tp%m;
        rep(i,0,4){
            int xx=tx+dx[i];
            int yy=ty+dy[i];
            if(xx<0||xx>=n||yy<0||yy>=m||s[xx][yy]=='#') continue;
            if(vis[xx][yy]) continue;
            vis[xx][yy]=vis[tx][ty]+1;
            p.push(xx*m+yy);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,0,n) scanf("%s",s[i]);
    bfs();
    int ans=n*m-vis[n-1][m-1];
    rep(i,0,n) rep(j,0,m) if(s[i][j]=='#') ans--;
    if(ans&1) puts("niuniu");
    else puts("niumei");
    return 0;
}