洛谷 P1387 最大正方形

 1 #include<cstdio>
 2 #include<iostream>
 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 }