给定一个n*n的字符矩阵,求出对称矩阵的最大边长(按左下到右上的对角线对称)
$f[i][j]:在(i,j)处,对称矩阵的最大边长$
$转移:t=f[i-1][j],表示右上角所能到达的最大边长,表示当前位置可以向左和向上找多少格$
$f[i][j]+1,当s[i-k][j]==f[i][j+1],1<=k<=t$
$当然f[i][j]最少是1$
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int ans;
int f[N][N];
char s[N][N];
int main()
{
while(cin >> n, n)
{
ans = 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin >> s[i][j];
memset(f, 0, sizeof f);
for(int i=1;i<=n;i++)
{
for(int j=n;j;j--)
{
f[i][j] = 1;
int t = f[i-1][j+1];
for(int k=1;k<=t;k++)
{
if(s[i-k][j] == s[i][j+k]) f[i][j] ++;
else break;
}
ans = max(ans, f[i][j]);
}
}
cout << ans << endl;
}
}