HDU 4618Palindrome Sub-Array(暴力枚举每一个正方形)

发布时间:2016-12-11 2:33:28 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4618Palindrome Sub-Array(暴力枚举每一个正方形)",主要涉及到HDU 4618Palindrome Sub-Array(暴力枚举每一个正方形)方面的内容,对于HDU 4618Palindrome Sub-Array(暴力枚举每一个正方形)感兴趣的同学可以参考一下。

Palindrome Sub-Array Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 933    Accepted Submission(s): 439 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.   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.   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 2013 Multi-University Training Contest 2                    题目大意:给你一个矩形,让你找出最大的正方形边长。使得任意行回文任意列回文。不敢直接暴力做。当时就在想用manacher解决。但是manacher需要的是字符,这个是int。看了题解居然真的是暴力枚举,泪流满面。。           解题思路:直接从边长最大开始从最小找。这点跟暴力KMP那个题目很像,然后就是暴力枚举每一个正方形的最左上的顶点,如果不满足,便移动这个顶点。详见代码。           题目地址:Palindrome Sub-Array AC代码: #include<iostream> #include<cstring> #include<string> #include<cstdio> using namespace std; int map1[305][305],n,m; int solve(int len) { int r1,r2,c1,c2,i,r11,r22,c11,c22; //c表示行r表示列 int flag1; for(c1=0;c1<=n-len;c1++) //行顶点 { for(r1=0;r1<=m-len;r1++) //列顶点 { flag1=0; r2=r1+len-1; c2=c1+len-1; for(i=c1;i<c1+len;i++) //c1~c1+len-1行都需要满足 { r11=r1,r22=r2; while(r11<=r22) { if(map1[i][r11]!=map1[i][r22]) { flag1=1; //有一行不满足 break; } if(flag1) break; r11++,r22--; } if(flag1) break; } if(flag1) continue; for(i=r1;i<r1+len;i++) //每一行满足了,再看每一列 { c11=c1,c22=c2; while(c11<=c22) { if(map1[c11][i]!=map1[c22][i]) { flag1=1; break; } if(flag1) break; c11++,c22--; } if(flag1) break; } if(flag1) continue; if(!flag1) return 1; } } return 0; } int main() { int tes,i,j,mi; scanf("%d",&tes); while(tes--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&map1[i][j]); mi=n; //mi记录min(n,m)即为可能的最大值 if(mi>m) mi=m; for(i=mi;i>=1;i--) { if(solve(i)) { printf("%d\n",i); break; } } } return 0; } //62MS 588K

上一篇:linux&nbsp;正则表达式基本函数
下一篇:世界微波射频领域传奇人物

相关文章

相关评论