嗯...

 

题目链接：https://www.luogu.org/problem/P1387

 

这道题有很多种做法，可以dp、暴力，而这里介绍的是前缀和做法。

首先输入后维护一个前缀和，然后遍历这个矩阵，当g[i][j]为1，l（边长）初始化为1，然后枚举边长伸长长度k，并且注意边界，然后对于每一个伸长后的矩形面积，进行差分，如果这个面积等于（k + 1） ^ 2，那么说明你现在这个状态它是一个正方形，边长++。然后ans取max即可。

 

AC代码：

1 #include
      
        2 #include
       
         3  4 using namespace std; 5 const int maxn = 205; 6 int n, m, g[maxn][maxn], s[maxn][maxn], l, ans; 7  8 int main(){ 9     scanf("%d%d", &n, &m);10     for(int i = 1; i <= n; i++){11         for(int j = 1; j <= m; j++){12             scanf("%d", &g[i][j]);13             s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + g[i][j];//前缀和 14         }15     }16     for(int i = 1; i <= n; i++){17         for(int j = 1; j <= m; j++){18             if(g[i][j]){19                 l = 1;//初始化 20                 ans = max(l, ans);21                 for(int k = 1; (k + i) <= n && (k + j) <= m; k++){
    //枚举伸长长度，判边界 22                     if(s[i + k][j + k] - s[i - 1][j + k] - s[i + k][j - 1] + s[i - 1][j - 1] == (k + 1) * (k + 1))//差分判断面积是否相同 23                         l++;//边长++ 24                         ans = max(ans, l);25                     }26                 }27             }28         }29     printf("%d\n", ans);30     return 0;31 }