链接：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;
}