hdu4618Palindrome Sub-Array(乱搞)

本文主要是介绍hdu4618Palindrome Sub-Array(乱搞)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

多校联赛第二场1008

结题报告上竟然给的是乱搞二字。

题意：从矩阵中找最大的正方形子矩阵使得每行每列的数字是符合回文。输出最大的边长。

1、动归

  状态；dp[i][j][k]表示以（I，j）为左上角坐标点且边长为k的子矩阵是否符合回文。

状态转移：dp[i][j][k] = 1 (如果dp[i-1][j-1][k-2]==1&&外围的四条边上的数字符合回文， 否则dp[i][j][k]=0)

dp[i-1][j-1][k-2]就是dp[i][j][k]的内层的小矩阵，为了使得dp[i][j][k]表示的矩阵符合条件，则小矩阵符合回文是状态转移的一个重要条件，

代码如下：

#include <cstdio>
#include <cstring>
#define M 310
int a[M][M];
bool dp[M][M][M];
int is_ok(int x, int y, int k)//验证外围的四条边是否回文
{for(int i = y, j = y+k-1; i < j; i++, j--)if(a[x][i]!=a[x][j]) return 0;for(int i = y, j = y+k-1; i < j; i++, j--)if(a[x+k-1][i]!=a[x+k-1][j]) return 0;for(int i = x, j = x+k-1; i < j; i++, j--)if(a[i][y]!=a[j][y]) return 0;for(int i = x, j = x+k-1; i < j; i++, j--)if(a[i][y+k-1]!=a[j][y+k-1]) return 0;return 1;
}
int main ()
{int t, n, m;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%d %d",&n,&m);for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){scanf("%d",&a[i][j]);dp[i][j][0] = 1;dp[i][j][1] = 1;}int len = n>m?m:n;int ans = 1;for(int k = 2; k <= len; k++)for(int i = 1; i+k-1 <= n; i++)for(int j = 1; j+k-1 <= m; j++){if(dp[i+1][j+1][k-2]&&is_ok(i,j,k)){dp[i][j][k] = 1;if(ans<k) ans = k;}}printf("%d\n",ans);}return 0;
}

2、暴力

就是对于边长从大到小的暴力即可l

代码如下：

#include <cstdio>
#define M 310
int a[M][M];
int ok(int x, int y, int k)
{for(int i = x; i-x<k; i++)for(int j = y, l = y+k-1; j < l; j++, l--)if(a[i][j]!=a[i][l])return 0;return 1;
}
int main ()
{int t, m, n;scanf("%d",&t);while(t--){scanf("%d %d",&n, &m);for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)scanf("%d",&a[i][j]);int len = n>m?m:n;int ans, f = 1;for(int k = len; f&&k >= 1; k--)for(int i = 1; f&&i+k-1 <= n; i++)for(int j = 1; f&&j+k-1 <= m; j++)if(ok(i, j, k)) {ans = k; f = 0;}printf("%d\n",ans);}return 0;
}

这篇关于hdu4618Palindrome Sub-Array(乱搞)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---