基于步数dp

题目传送门

大致思路

可以发现"gcd"只有六种排列,一旦确定某种排列之后,每一步要走到的字母就确定了
记dp[i][j]为到(i,j)格有几种路径

$$dp[i][j]=dp[i][j-1]+dp[i-1][j] $$

做六次dp,累加即可

Code

void solve() {
    int n,ans=0;
    cin >> n;
    int k=(2*n-1)/3;
    vector<string > a(n);
    for(int i=0;i<n;i++) cin >>a[i];
    string bzd[]={"gcd","gdc","dgc","dcg","cdg","cgd"};
    for(auto zyy : bzd){
        char c1=zyy[0],c2=zyy[1],c3=zyy[2];
        if(a[0][0]!=c1 || a[n-1][n-1]!=c3) continue;
        vector <vector<int>> dp(n,vector<int>(n,0));
        dp[0][0]=1;
        for(int w=1;w<2*n-1;w++){
            for(int i=0;i<n;i++){
                int j=w-i;
                if(j<0 || j>=n) continue;
                char need;//这一步应该走到哪一个字母
                if(w<k) need=c1;
                else if(w<2 * k && w>=k) need=c2;
                else need=c3;
                if(a[i][j]!=need) continue;
                int temp=0;
                if(i>0) temp = (temp+dp[i-1][j]) % MOD;
                if(j>0) temp = (temp + dp[i][j-1] ) %MOD;
                dp[i][j]=temp;
            }
        }
        ans=(ans+dp[n-1][n-1])%MOD;
    }
    cout << ans << el;
}