HDU 2859 Phalanx

Phalanx

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 776 Accepted Submission(s): 359

Problem Description

Today is army day, but the servicemen(技工) are busy with the phalanx(趾骨) for the celebration of the 60th anniversary(周年纪念日) of the PRC.
A phalanx is a matrix(矩阵) of size n*n, each element(元素) is a character (a~z or A~Z), standing for the military(军事的) branch of the servicemen on that position.
For some special requirement it has to find out the size of the max symmetrical(匀称的) sub-array. And with no doubt, the Central Military Committee gave this task to ALPCs.
A symmetrical(匀称的) matrix(矩阵) is such a matrix that it is symmetrical by the “left-down to right-up” line. The element(元素) on the corresponding place should be the same. For example, here is a 3*3 symmetrical matrix:
cbx
cpb
zcc

Input

There are several test cases in the input(投入) file. Each case starts with an integer(整数) n (0<n<=1000), followed by n lines which has n character. There won’t be any blank spaces between characters or the end of line. The input file is ended with a 0.

Output

Each test case output(输出) one line, the size of the maximum symmetrical sub- matrix.

Sample Input

3
abx
cyb
zca
4
zaba
cbab
abbc
cacq
0

Sample Output

3
3

这个题目是找最大的均匀矩阵。这个均匀矩阵的特点是由右上角到左下角确定的对角线两边对称。

一开始傻了，按着左上角找转移方程，但是其实从右上角开始找才是最明智的。

dp[i][j]表示以当前点为左下角的矩阵最大的规模，首先，第一行和最后一列的所有元素一定都是1，我们从第2行开始遍历，我们如果仔细观察会发现对应(i, j)这个点的特殊点在(i - 1, j + 1)，也就是它的右上的那个点，如果当前的点上面的点依次与当前的点右面的点在以特殊点确定的最大矩阵规模的范围内相同的话，那么我们就可以得出当前点的值。

举个例子

a	b	c
a	d	b
g	t	a

我们计算对于以左下角为当前位置的矩阵最大规模的时候，我们发现它的右上那个格子，也就是d对应的格子，它的矩阵规模是2，那么我们就在2的范围内比较当前位置的上面的和右面的元素即可（超过了2的话肯定不行，因为d能确定的最大的是2，如果还可以往下比较的话那么d能确定的矩阵应该更大，才能保证当前位置确定的矩阵的右上角是对称的），发现a和t不同，那么当前位置就是1

相反如下图：

a	b	c
t	d	b
g	t	a

我们在2这个范围内比较以后发现一直比较到最后都是相同的，我们只需要对d对应的规模加1赋值即可

另外注意当1 * 1的矩阵的规模是1.

代码如下：

/*************************************************************************
	> File Name: Phalanx.cpp
	> Author: Zhanghaoran
	> Mail: chilumanxi@xiyoulinux.org
	> Created Time: Wed 28 Oct 2015 07:40:07 PM CST
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>

using namespace std;

int dp[1010][1010];
char a[1010][1010];
int N;

int main(void){
    while(1){
        scanf("%d", &N);
        if(N == 0)
            break;
        getchar();
        int Max = 0;
        for(int i = 0; i < N; i ++){
            for(int j = 0; j < N; j ++){
                scanf("%c", &a[i][j]);
            }
            getchar();
        }
        if(N == 1){
            printf("1
");
            continue;
        }
        
        for(int i = 0; i < N; i ++){
            dp[0][i] = 1;
            dp[i][N - 1] = 1;
        }
        
        for(int i = 1; i < N; i ++){
            for(int j  = 0; j < N - 1; j ++){
                int temp;
                int flag = 0;
                for(temp = 1; temp <= dp[i - 1][j + 1]; temp ++){
                    if(a[i - temp][j] != a[i][j + temp]){
                        flag = 1;
                        break;
                    }
                }
                if(flag)
                    dp[i][j] = temp;
                else 
                    dp[i][j] = dp[i - 1][j + 1] + 1;
                if(Max < dp[i][j])
                    Max = dp[i][j];
            }
        }
        //for(int i = 0 ; i < N; i ++){
        //    for(int j = 0; j < N; j ++)
        //        cout << dp[i][j];
        //    cout << endl;
        //}
        printf("%d
", Max);
    }
}