「ある領域が点対称に塗られていること」の同値な言い換えを考えてみます。

領域 \((h _ 1,h _ 2,w _ 1,w _ 2)\) が点対称に塗られていることは、以下のすべての条件が満たされていることと同値です。

• マス \((h _ 1,w _ 1)\) とマス \((h _ 2,w _ 2)\) が同じ色で塗られている
• マス \((h _ 1,w _ 2)\) とマス \((h _ 2,w _ 1)\) が同じ色で塗られている
• \(h _ 1+1\le h _ 2-1\) なら、領域 \((h _ 1+1,h _ 2-1,w _ 1,w _ 2)\) が点対称に塗られている
• \(w _ 1+1\le w _ 2-1\) なら、領域 \((h _ 1,h _ 2,w _ 1+1, w _ 2-1)\) が点対称に塗られている。

あとは、これをメモ化再帰などで実装することでこの問題を解くことができます。 時間計算量は \(O(H ^ 2W ^ 2)\) などとなります。 メモ化再帰などを使うと空間計算量も \(O(H ^ 2W ^ 2)\) となりますが、中心を固定して伸ばしていくような実装を行うと空間計算量を \(O(HW)\) とすることもできます。

実装例は以下のようになります。 以下の実装例は std::map を用いたメモ化再帰を行っているため、時間計算量は \(O(H ^ 2W ^ 2\log HW)\) 、空間計算量は \(O(H ^ 2W ^ 2)\) となっています。

#include <vector>
#include <iostream>
#include <ranges>
#include <map>

int main() {
    using namespace std;
    unsigned H, W;
    cin >> H >> W;
    vector<string> board(H);
    for (auto&& row : board)
        cin >> row;

    // メモ化再帰で (h1, h2, w1, w2) が点対称に塗られているか判定する
    map<tuple<unsigned, unsigned, unsigned, unsigned>, bool> memo{};
    const auto solve{[&board, &memo](this auto& rec, unsigned h1, unsigned h2, unsigned w1, unsigned w2) -> bool {
        if (memo.contains({h1, h2, w1, w2}))
            return memo[{h1, h2, w1, w2}];
        return memo[{h1, h2, w1, w2}] = board[h1][w1] == board[h2][w2] && board[h1][w2] == board[h2][w1] && (h1 + 1 < h2 ? rec(h1 + 1, h2 - 1, w1, w2) : true) && (w1 + 1 < w2 ? rec(h1, h2, w1 + 1, w2 - 1) : true);
    }};

    unsigned ans{};
    for (unsigned h1{}; h1 < H; ++h1)
        for (unsigned h2{h1}; h2 < H; ++h2)
            for (unsigned w1{}; w1 < W; ++w1)
                for (unsigned w2{w1}; w2 < W; ++w2)
                    ans += solve(h1, h2, w1, w2);

    cout << ans << endl;
    return 0;
}