Z-Game on grid

题目链接
题意：
1：给出n*m的矩阵
2：矩阵中有’A’,‘B’,'.'Three types of characters
3：Alice先手,Bob后手
4：You can only move right or down each time,and cannot exceed the matrix
5：遇到A,Alice赢,遇到B,BobIn the end, it is a draw with no one facing each other
6：问最终谁赢
题解：I thought it was a rule,But no matter how you find it, you can't always find all the cases,It was only after the game that I found out that it wasdfs记忆化搜索.

我们可以发现(i+j)When it is an even numberAlice走,另外一种情况是Bob走.

AliceThe purpose is to achieve the state he wants,而BobThe purpose is to destroy his state or to achieve his own state,但是因为是Alice先手,所以Bobshould be destroyingAlicestate when you reach your state.

Because the final state has3个,win,lose,平局.所以我们dfs即可,Suppose that the state he wants is the above three,Violence is enough.

Because it resembles violence,So there must be an answer

下面是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;//Indicates the current expected value,The value that can be run if both are positive
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,Feel free to return to a state,Arbitrary values ​​cannot be returned here,因为Alice和BobThe states are obtained from each other,所以AliceThe unwanted state isBob想要的
        if(ans1!=0) return ans1;
        else return ans2;
        //The above must be or not0的情况下,因为有可能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,Feel free to return a value
        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;
}

总结：When thinking about nothing,If you can't think of anything other than violence,Then the question is violence,We should think about how to optimize violence,This question is optimized using memoized search.