特别水一道题,还写错了。每行维护一个前缀和,枚举矩形的左上角,扫矩阵第一行的长度,然后看这个长度能向下维持几行。但是忘记考虑要向上也扫一下能维持几行,再求一个和的。因为可能1的长度是逐行递减的,下面的矩形可以向上延申。
1 #include2 #include 3 using namespace std; 4 int n,m,res; 5 int mp[110][110]; 6 int main() 7 { 8 scanf("%d%d",&n,&m); 9 for (int i = 1;i <= n;i++)10 for (int j = 1;j <= m;j++)11 scanf("%d",&mp[i][j]);12 for (int i = 1;i <= n;i++)13 for (int j = 1;j <= m;j++)14 mp[i][j] += mp[i][j - 1];15 for (int i = 1;i <= n;i++)16 for (int j = 1;j <= m;j++)17 {18 if (mp[i][j] - mp[i][j - 1] == 0) 19 continue;20 int o,k,t;21 for (o = j;mp[i][o + 1] > mp[i][o];o++);22 for (k = i;mp[k + 1][o] - mp[k + 1][j - 1] == o - j + 1;k++);23 for (t = i;mp[t - 1][o] - mp[t - 1][j - 1] == o - j + 1;t--);24 res = max(res,min(o - j,k - t) + 1);25 }26 printf("%d\n",res);27 return 0;28 }