[dp+博弈]棋盘的必胜策略

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=1e2+1;
 4 char mp[51][51];
 5 int dp[51][51][amn],r,c,k,dic[5][3]={{0,1},{0,-1},{1,0},{-1,0}},dx,dy,si,sj;
 6 int dfs(int x,int y,int k){
 7     if(k<=0||mp[x][y]=='E')return dp[x][y][k]=0;///如果上一个牛把牌移动到了当前这个点使得牌的k变为0或到达终点，则现在这只牛就输了，返回一个0
 8     if(dp[x][y][k]!=-1)return dp[x][y][k];      ///如果这个点被走过了，返回这个状态      
 9     for(int i=0;i<4;i++){
10         dx=x+dic[i][0];
11         dy=y+dic[i][1];
12         if(dx>=1&&dx<=r&&dy>=1&&dy<=c&&mp[dx][dy]!='#'&&k>0&&!dfs(dx,dy,k-1))    ///若从这个点出发，能走在棋盘内且还剩余步数，下一步能走到一个点使下一个牛输，则此点是可使这个牛赢的点
13             return dp[x][y][k]=1;
14     }
15     return dp[x][y][k]=0;                       ///若从这个点出发，下一步走不到一个点使下一个牛输的点，则此点是可使这个牛输的点
16 }
17 int main(){
18     ios::sync_with_stdio(0);
19     cin>>r>>c>>k;
20     for(int i=1;i<=r;i++){
21         for(int j=1;j<=c;j++){
22             cin>>mp[i][j];
23             if(mp[i][j]=='T'){si=i,sj=j;}
24         }
25     }
26     memset(dp,-1,sizeof dp);
27     if(dfs(si,sj,k)==1)printf("niuniu\n");  ///如果从起点出发能到达一个必胜状态，则先手必胜
28     else printf("niumei\n");
29 }
30 /***
31 一个r行c列的二维棋盘，有障碍物‘#’和空地‘.’,有多个出口’E‘和一个起点’T‘,从起点开始可以走k步，若k变为0时则把牌的k变为0的这个牛取胜，若能在k步或k步内到达任意一个终点E，则把牌移动到终点的那个牛胜，现在牛牛先手，问牛牛能否必胜
32 如果从起点出发能到达一个必胜状态，则先手必胜
33 现在从起点开始搜索周围的点
34 先看这个点如果上一个牛把牌移动到了当前这个点使得牌的k变为0或到达终点，则现在这只牛就输了，返回一个0
35 若这个点不发货上述条件，则再从这个点出发，看周围上下左右的点，若能走在棋盘内且还剩余步数，下一步能走到一个点使下一个牛输，则此点是可使这个牛赢的点，否则，若从这个点出发，下一步走不到一个点使下一个牛输的点，则此点是可使这个牛输的点
36 ***/