Niitty

output/ccFuBUzg.o: in function `check(std::pair<int, int>, std::pair<int, int>)':
code.cpp:(.text+0x22d): relocation truncated to fit: R_X86_64_PC32 against symbol `z' defined in .bss section in output/ccFuBUzg.o
code.cpp:(.text+0x24b): relocation truncated to fit: R_X86_64_PC32 against symbol `K' defined in .bss section in output/ccFuBUzg.o
output/ccFuBUzg.o: in function `haku()':
code.cpp:(.text+0x395): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in output/ccFuBUzg.o
code.cpp:(.text+0x3e0): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in output/ccFuBUzg.o
code.cpp:(.text+0x491): relocation truncated to fit: R_X86_64_PC32 against symbol `counter' defined in .bss section in output/ccFuBUzg.o
output/ccFuBUzg.o: in function `main':
code.cpp:(.text.startup+0x3e): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in output/ccFuBUzg.o
code.cpp:(.text.startup+0x57): relocati...

#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define forN(i,k,n) for(int i=k;i<n;++i)
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define inf ((int)(1.01e9))
#define N ((int)(505))

int n, letters, L, counter;
char a[N][N];
int z[26][N][N], K[26];
bool vis[N][N][N][N];

unordered_map<ll, bool> mem;

bool check(pii l, pii r) {
    int c;
    forn(h,26) if (K[h]) {
        c = z[h][r.F+1][r.S+1] - z[h][l.F][r.S+1] 
            - z[h][r.F+1][l.S] + z[h][l.F][l.S];
        if (!c) return false;
    }
    return true;
}


void haku() {
    queue<pair<pii,pii>> bfs;
    bfs.push({{0, 0}, {n-1, n-1}});
    vis[0][0][n-1][n-1]=1;

    while (bfs.size()) {
        auto [l, r] = bfs.front();
        bfs.pop();

        //if (mem.find(l.F+l.S*32157+r.F*32094280+r.S*283242473) != mem.end()) 
         //   return;
        if (!check(l, r)) continue;

        counter++;
        //mem[l.F+l.S*32157+r.F*32094280+r.S*283242473]=1;
        

        //cout<<l.F<<' '<<l.S<<endl<<r.F<<' '<<r.S<<endl<<endl;

        // 0
        if (l.F < r.F && !vis[l.F+1][l.S][r.F][r.S]) {
            vis[l.F+1][l.S][r.F][r.S]=1;
            bfs.push({{l.F+1,l.S}, r});
        }
        // 1
        if (l.S < r.S && !vis[l.F][l.S+1][r.F][r.S]) {
            vis[l.F][l.S+1][r.F][r.S]=1;
            bfs.push({{l.F,l.S+1}, r});
        }
        // 2
        if (l.F < r.F && !vis[l.F][l.S][r.F+1][r.S]) {
            vis[l.F][l.S][r.F+1][r.S]=1;
            bfs.push({l, {r.F+1, r.S}});
        }
        // 3
        if (l.S < r.S && !vis[l.F][l.S][r.F][r.S+1]) {
            vis[l.F][l.S][r.F][r.S+1]=1;
            bfs.push({l, {r.F, l.S+1}});
        }
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    
    cin >> n;
    forn(i,n) forn(j,n) {
        char ina;
        cin >> ina;
        a[i][j] = ina;
        K[ina-'A']++;
    }

    forn(k, 26) forn(i,n) forn(j,n) {
        z[k][i+1][j+1] = z[k][i][j+1] + z[k][i+1][j] - z[k][i][j];
        z[k][i + 1][j + 1] += (a[i][j] == 'A'+k);
    }

    forn(i,26) if (K[i]) letters++; 
    L = letters;
    counter = 0;

    haku();
    
    cout << counter << endl;
}