PALINCROSS (lqdoj)

#include <bits/stdc++.h>
using namespace std;
#define x1 sdvksvkdslvlksdv
#define x2 sdjvdsvdbdfbfbrr
#define y1 sdvddfbsgrebdsvd
#define y2 sjdvsdvsdbdfbfbb
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int n, m;
char a[50][50];
int dp[50][50][50][50];
int mx1[2] = {0,-1};
int my1[2] = {-1,0};
int mx2[2] = {0,1};
int my2[2] = {1,0};

bool ok(int x,int y) {
    return 0<=x && x<n && 0<=y && y<n;
}

int caldp(int x1,int y1,int x2,int y2) {
#define STATE x1][y1][x2][y2
    if (dp[STATE]!=-1) return dp[STATE];

    int curLength = (tie(x1,y1)==tie(x2,y2)) ? 1 : 2;

    dp[STATE] = curLength;
    rep(i,0,2) rep(j,0,2) {
        int nx1 = x1 + mx1[i], ny1 = y1 + my1[i];
        int nx2 = x2 + mx2[j], ny2 = y2 + my2[j];
        if (ok(nx1, ny1) and ok(nx2, ny2) and a[nx1][ny1] == a[nx2][ny2]) dp[STATE] = max(dp[STATE], caldp(nx1,ny1,nx2,ny2) + curLength);
    }

    return dp[STATE];

}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n;
    rep(i,0,n) rep(j,0,n) cin >> a[i][j];
    memset(dp,-1,sizeof(dp));

    int res = 0;
    rep(i,0,n) rep(j,0,n) res = max(res, caldp(i,j,i,j));
    //cout << res << '\n';
    rep(i,0,n) rep(j,0,n) {
        if (i+1<n and a[i][j]==a[i+1][j]) res = max(res, caldp(i,j,i+1,j));
        if (j+1<n and a[i][j]==a[i][j+1]) res = max(res, caldp(i,j,i,j+1));
    }
    cout << res;
}