将问题转化一下, 其实就是在 01 矩阵中找边长最大的正方形 (对角线长在此等于边长), 这和那道最大正方形很像. 因为当时最大正方形用的是一种比较落后的思想, 所以这道题也没有顺利 A 掉. 其实这道题的思路还是很容易理解的, 先讨论左上到右下的对角线, 我们定义 dp[i][j] 表示以 (i,j) 为右下角的最大正方形的边长, l1(i,j)表示从 (i,j) 往左最多有几个连续的 0,l2(i,j)表示从 (i,j) 往上最多有几个连续的 0, 那么当 map[i][j]==1 时, 则有 dp[i][j]=min(dp[i-1][j-1],min(l1[i][j-1],l2[i-1][j]))+1. 因为要保证这个正方形中只有对角线上是 1 且全是 1. 然后再修改一下 l1, 使其保存从 (i,j) 往右最多有几个连续的 0, 再从右上到左下跑一边 DP, 比较两次的最大值就 OK 了. 因为最大正方形那道题里, 最大正方形要求里面全是 1, 而这里要求对角线全是 1, 且其他地方不能有 1, 因此我们就需要预处理一下相对于 dp[i-1][j-1]多出来的边框, 而不能简单地利用 dp[i][j-1]和 dp[i-1][j].
- #include<cstdio>
- inline int min(int a,int b) {return a<b?a:b;}
- inline int max(int a,int b) {return a>b?a:b;}
- const int mmax=2505;
- int n,m,map[mmax][mmax],l1[mmax][mmax],l2[mmax][mmax],dp[mmax][mmax],ans;
- int main() {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j) {
- scanf("%d",&map[i][j]);
- if(!map[i][j]) l1[i][j]=l1[i][j-1]+1,l2[i][j]=l2[i-1][j]+1;
- }
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j)
- if(map[i][j]) {
- dp[i][j]=min(dp[i-1][j-1],min(l1[i][j-1],l2[i-1][j]))+1;
- ans=max(ans,dp[i][j]);
- }
- for(int i=1;i<=n;++i)
- for(int j=m;j>=1;--j) if(!map[i][j]) l1[i][j]=l1[i][j+1]+1;
- for(int i=1;i<=n;++i)
- for(int j=m;j>=1;--j)
- if(map[i][j]) {
- dp[i][j]=min(dp[i-1][j+1],min(l1[i][j+1],l2[i-1][j]))+1;
- ans=max(ans,dp[i][j]);
- }
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2763130.html