E

题目链接[小红的gcd](https://ac.nowcoder.com/acm/contest/123787/E)

思路

根据左上角的字符和右下角的字符可以很容易确定中间的字符是什么，进而确定最终得到的字符串 S。
如果左上角的字符和右下角的字符相同，易知答案为 0。

在确定了字符串 S 后，考虑动态规划，定义 dp[i][j] 表示从 (1,1) 走到 (i,j) 的合法路径数量，合法指从 (1,1) 走到 (i,j) 所得字符串为 S 的前缀。

为此我们还需要知道从 (1,1) 走到 (i,j) 共走过了多少步（设为 dis），即 (i,j) 对应的是 S 的第 dis 个字符，不难看出：

dis = i + j - 1

状态转移方程：

1. 若 a[i][j] != S[dis]（注意这里 S 为 1-indexed）
   dp[i][j] = 0

2. 若 a[i][j] == S[dis]
dp[i][j] = dp[i-1][j] + dp[i][j-1]

答案即为 dp[n][n]，注意取模。

代码（屎山代码不喜轻喷QAQ）：

//
// Created by Dan on 2025/10/14.
//
#include <bits/stdc++.h>


//#pragma GCC optimize(2)
using namespace std;

#define ull unsigned long long
#define PII pair<long long ,long long >
#define PIII pair<int, pair<int,int>>
#define pll pair<long long,long long>
#define f1n(x, n) for (int x = 1; x <= n; ++x)
#define fff(x, s, n) for (int x = s; x <= n; ++x)
#define ffr(x, s, t) for (int x = s; x >= t; --x)
#define f0n(x, n) for (int x = 0; x < n; ++x)
#define fn0(x, n) for(int x = n-1; x>=0; x--)
#define fn1(x, n) for(int x = n; x>0; x--)
#define double long double
//#define vector deque
#define vi vector<int>
#define LL long long
#define ll long long
#define int long long
#define vl vector<int>
#define vd vector<double>
#define vvl vector<vector<int>>
#define vvvl vector<vector<vector<int>>>
#define vv(type) vector<vector<type>>
#define vp vector<pair<ll,ll>>
#define nvvl(n, m) vector<vector<int>>(n,vector<int>(m,0))
#define nvvvl(n, m, t) vector<vector<vector<int>>>(n,vector<vector<int>>(m,vector<int>(t)))
#define nvvlt(n, m, t) vector<vector<t>>(n,vector<t>(m,0))
#define nvvlv(n, m, v) vector<vector<int>>(n,vector<int>(m,v))
int mod = 998244353;
const int inf = 1e18;
//#define endl '\n'

void init() {

}


void solve() {
    int n;
    cin >> n;
    vvl a = nvvl(n + 2, n + 2);
    vvl dp = nvvl(n + 2, n + 2);
    f1n(i, n) {
        f1n(j, n) {
            char c;
            cin >> c;
            a[i][j] = c;
        }
    }
    int k = (2 * n + 1) / 3;
    int x = 'g' ^ 'c' ^ 'd';
    x ^= a[1][1];
    x ^= a[n][n];
    dp[1][1] = 1;
    f1n(i,n){
        f1n(j,n){
            if (i==1&&j==1)
                continue;
            int dis = i+j;
            int c;
            if (dis<=k+1)
                c = a[1][1];
            else if (dis<=2*k+1)
                c = x;
            else
                c = a[n][n];
            if (a[i][j] !=c)
                continue;
            dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod;
        }
    }
    cout<<dp[n][n]<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;

    init();
    while (t--) {
        solve();
    }
}