HDU 2859：最大反對稱子矩陣 - 動態規劃

題目描述

給定 n×n 字符矩陣（字符為 a-z 或 A-Z），尋找最大的「反對稱」子矩陣大小。反對稱定義：沿「左下到右上」對角線（副對角線）對稱，即 mat[i][j] == mat[n-1-j][n-1-i]（以 0 為基準）。輸入多組測試，n=0 結束。

解題思路

定義 dp[i][j] 為以 (i,j) 為右下角的最大正方形反對稱子矩陣邊長。狀態轉移：

• 若 mat[i][j] 與其對應的副對角線位置字符匹配，且內層子矩陣也反對稱，則邊長可擴展。
• 具體檢查：對於 k = 1..dp[i-1][j+1]，需 mat[i-k][j] == mat[i][j+k]。若全匹配，dp[i][j] = dp[i-1][j+1] + 1；否則在首個失配處截斷。

最終答案為所有 dp[i][j] 的最大值。複雜度 O(n³)，對 n ≤ 1000 可接受。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int dp[N][N];
char mat[N][N];

int main() {
    int n;
    while (~scanf("%d", &n), n) {
        for (int i = 1; i <= n; ++i) {
            scanf("%s", mat[i] + 1);
            for (int j = 1; j <= n; ++j) dp[i][j] = 1;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                int m = dp[i-1][j+1];
                bool flag = true;
                int x = 0;
                for (int k = 1; k <= m; ++k) {
                    if (mat[i-k][j] == mat[i][j+k]) continue;
                    flag = false; x = k; break;
                }
                dp[i][j] = flag ? m + 1 : x;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                ans = max(ans, dp[i][j]);
        printf("%d\n", ans);
    }
    return 0;
}