Z-Game on grid(牛客多校赛)

题目链接
题意：
1：给出n*m的矩阵
2：矩阵中有’A’，‘B’，'.'三种类型的字符
3：Alice先手，Bob后手
4：每次只能向右或向下移动，且不能超过矩阵
5：遇到A，Alice赢，遇到B，Bob赢最终谁也没遇到就是平局
6：问最终谁赢
题解：本来以为是找规律，但是不管怎么找到总是不能将所有的情况都找出来，赛后才知道原来是dfs记忆化搜索。

我们可以发现(i+j)为偶数的时候该Alice走，另外一种情况是Bob走。

Alice的目的是达到他想要的一种状态，而Bob的目的是破坏他这种状态或达到自己的状态，但是因为是Alice先手，所以Bob应该是在破坏Alice状态的时候达到自己的状态。

因为最终的状态有3个，win，lose，平局。所以我们dfs即可，假设他想要的状态是以上三种，分别暴力即可。

因为这样类似与暴力，所以肯定是可以找出答案的

下面是AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
char s[550][550];
int dp[550][550];//1表示win，2表示平局，3表示输
int want=0;//表示当前的期望值，在两者都积极的情况下能够跑到的值
int n,m;
bool check(int x,int y)
{
    
    if(x>n||x<1||y>m||y<1) return false;
    return true;
}
int dfs(int x,int y)
{
    
    if(s[x][y]=='B') return 3;
    if(s[x][y]=='A') return 1;
    if(x==n&&y==m) return 2;
    if(dp[x][y]!=-1) return dp[x][y];
    if((x+y)%2==0)//该A走了
    {
    
        int ans1=0,ans2=0;
        if(check(x+1,y))
        {
    
            ans1=dfs(x+1,y);
            if(ans1==want) return dp[x][y]=want;
            //cout<<x<<" "<<y<<" "<<ans1<<"-->"<<endl;
        }
        if(check(x,y+1))
        {
    
            ans2=dfs(x,y+1);
            if(ans2==want) return dp[x][y]=want;
            //cout<<x<<" "<<y<<" "<<ans2<<"-->"<<endl;
        }
        //如果没有得到want,随意返回一种状态即可，这里不能回复随意的值，因为Alice和Bob的状态是互相得到的，所以Alice不想要的状态是Bob想要的
        if(ans1!=0) return ans1;
        else return ans2;
        //以上一定是要不为0的情况下，因为有可能check为false的时候越界了，这样就不会得到ans的值，ans=0
    }
    else//该B走了
    {
    
        int ans1=0,ans2=0;
        if(check(x+1,y))
        {
    
            ans1=dfs(x+1,y);
            //cout<<x<<" "<<y<<" "<<ans1<<"-->"<<endl;
            if(ans1!=want) return dp[x][y]=ans1;
        }
        if(check(x,y+1))
        {
    
            ans2=dfs(x,y+1);
            //cout<<x<<" "<<y<<" "<<ans2<<"-->"<<endl;
            if(ans2!=want) return dp[x][y]=ans2;
        }
        //如果没有得到want,随意返回值即可
        if(ans1!=0) return ans1;
        else return ans2;
    }
}
int main()
{
    
    int t;
    cin>>t;
    while(t--)
    {
    
        cin>>n>>m;
        for(int i=1; i<=n; i++) cin>>s[i]+1;
        want=1;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                dp[i][j]=-1;
        if(dfs(1,1)==1) cout<<"yes ";
        else cout<<"no ";
        want=2;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                dp[i][j]=-1;
        if(dfs(1,1)==2) cout<<"yes ";
        else cout<<"no ";
        want=3;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                dp[i][j]=-1;
        if(dfs(1,1)==3) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

总结：在想没道题的时候，如果除了暴力其余的情况怎么想都不能完全想出来，那么这道题就是暴力，我们应该想着如何优化暴力，这道题就是用的记忆化搜索来优化的。