棋盘的必胜策略（博弈+搜索）

链接：

https://ac.nowcoder.com/acm/problem/21797
来源：牛客网

题目描述

有一个二维棋盘，棋盘有r行c列，棋盘中的每一个位置有如下四种情况
'E': 表示出口，可能有多个
'T': 只有一个，表示起点
'#': 表示障碍
'.': 表示空地

牛牛和牛妹在这样一个棋盘上玩游戏，他们有一张写有整数k的卡片，一开始放置在起点的位置，现在牛牛和牛妹开始轮流操作，牛牛先操作
当前操作的牛会选择上下左右其中一个方向移动卡片，每走一步，卡片上的数字减去1
只能走到空地上，或者走到出口，走到出口，游戏就会结束，卡片的数字变成0的时候游戏也会结束，不能再移动的牛会输掉游戏

如果牛牛和牛妹都用最佳策略，请问谁会赢

输入描述:

第一行输入3个整数r,c,k
接下来r行每行读入k个字符表示棋盘

1 ≤ r,c ≤ 50, 1 ≤ k ≤ 100

输出描述:

如果牛牛有必胜策略，输出"niuniu"否则输出"niumei"

具体思路：

博弈+搜索，暴力就完事了（这题凑样例都能过83）

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 # define LL_inf (1ll<<60)
 6 const int maxn = 200;
 7 char str[55][55];
 8 int r,c,k;
 9 struct node
10 {
11     int x,y,step;
12     node() {}
13     node(int xx,int yy,int zz)
14     {
15         x=xx,y=yy,step=zz;
16     }
17 };
18 int f[2][4]= {{1,-1,0,0},{0,0,1,-1}};
19 bool judge(int x,int y)
20 {
21     return x>=1&&x<=r&&y>=1&&y<=c&&str[x][y]!='#';
22 }
23 int dp[55][55][maxn];
24 bool dfs(int st,int ed,int k)
25 {
26     if(str[st][ed]=='E')return dp[st][ed][k]=0;// 当为'E'的时候，这个时候对于后手是必败态，对于先手就是必胜态
27     if(k<=0)
28         return 0;
29     if(dp[st][ed][k]!=-1)
30         return dp[st][ed][k];
31     for(int i=0; i<4; i++)
32     {
33         int tx=st+f[0][i];
34         int ty=ed+f[1][i];
35         if(judge(tx,ty)&&k-1>=0)
36         {
37             if(dfs(tx,ty,k-1)==0)
38                 return  dp[st][ed][k]=1;
39         }
40     }
41     return dp[st][ed][k]=0;
42 }
43 int main()
44 {
45     memset(dp,-1,sizeof(dp));
46     int st,ed;
47     scanf("%d %d %d",&r,&c,&k);
48     for(int i=1; i<=r; i++)
49     {
50         scanf("%s",str[i]+1);
51         for(int j=1; j<=c; j++)
52         {
53             if(str[i][j]=='T')
54             {
55                 st=i,ed=j;
56             }
57         }
58     }
59     int ans=dfs(st,ed,k);
60     printf("%s
",ans==1?"niuniu":"niumei");
61     return 0;
62 }