Palindrome Sub-Array
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 162 Accepted Submission(s): 72
Problem Description
A palindrome sequence is a sequence which is as same as its reversed order. For example, 1 2 3 2 1 is a palindrome sequence, but 1 2 3 2 2 is not. Given a 2-D array of N rows and M columns, your task is to find a maximum sub-array of P rows and P columns,
of which each row and each column is a palindrome sequence.
of which each row and each column is a palindrome sequence.
Input
The first line of input contains only one integer, T, the number of test cases. Following T blocks, each block describe one test case.
There is two integers N, M (1<=N, M<=300) separated by one white space in the first line of each block, representing the size of the 2-D array.
Then N lines follow, each line contains M integers separated by white spaces, representing the elements of the 2-D array. All the elements in the 2-D array will be larger than 0 and no more than 31415926.
There is two integers N, M (1<=N, M<=300) separated by one white space in the first line of each block, representing the size of the 2-D array.
Then N lines follow, each line contains M integers separated by white spaces, representing the elements of the 2-D array. All the elements in the 2-D array will be larger than 0 and no more than 31415926.
Output
For each test case, output P only, the size of the maximum sub-array that you need to find.
Sample Input
1 5 10 1 2 3 3 2 4 5 6 7 8 1 2 3 3 2 4 5 6 7 8 1 2 3 3 2 4 5 6 7 8 1 2 3 3 2 4 5 6 7 8 1 2 3 9 10 4 5 6 7 8
Sample Output
4
Source
Recommend
zhuyuanchen520
直接暴力，不过要注意break的地方，防止超时！
没什么技术含量！
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int map[330][330];
int rec[330];
int n,m;
int ans;
int is_ok(int i,int j,int len)
{
int k=0;
len--;
while(k<len)
{
if(map[i][j+k]!=map[i][j+len])
return 0;
k++,len--;
}
return 1;
}
int is_ok_ver(int i,int j,int len)
{
int k=i+len-1;
while(i<k)
{
if(map[i][j] !=map[k][j])
return 0;
i++,k--;
}
return 1;
}
int is_matrix(int i,int j,int len)
{
int k,r;
for(k=0;k<len;k++)
{
if(!is_ok(i+k,j,len))
return 0;
if(!is_ok_ver(i,j+k,len))
return 0;
}
return 1;
}
int find_ans(int i,int j)
{
int p=n-i,q=m-j,len;
len= p < q ? p : q;
if(ans >= len)
return 0;
while(len > ans)
{
if(is_matrix(i,j,len))
{
ans=len;
return 0;
}
len--;
}
return 1;
}
int main()
{
int t,i,j,k;
scanf("%d",&t);
while(t--)
{
ans=1;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&map[i][j]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
find_ans(i,j);
}
printf("%d\n",ans);
}
return 0;
}