A9 二维前缀和 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P1387 ↗

题目描述

在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数 $n,m(1\leq n,m\leq 100)$ ，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开， $0$ 或 $1$ 。

输出格式

一个整数，最大正方形的边长。

输入输出样例

输入 #1

plaintext

输出 #1

plaintext

算法解析#

EH在偷偷开摆

Python代码实现#

a = [[0 for i in range(103)] for j in range(103)]
b = [[0 for i in range(103)] for j in range(103)]
n, m = map(int, input().split())
for i in range(1, n + 1):
    temp = list(map(int, input().split()))
    for j in range(1, m + 1):
        a[i][j] = temp[j - 1]
        b[i][j] = b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j]
ans = 1
for l in range(2, min(m, n) + 1):
    for i in range(l, n + 1):
        for j in range(l, m + 1):
            if b[i][j]-b[i-l][j]-b[i][j-l]+b[i-l][j-l] == l * l:
                ans = l
print(ans)

python

C++代码实现#

#include <algorithm>
#include <iostream>
using namespace std;

int a[103][103];
int b[103][103];

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++){
      cin>>a[i][j];
      b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];
    }

  int ans=1;
  for(int l=2;l<=min(n,m);l++)
    for(int i=l; i<=n; i++)
      for(int j=l; j<=m; j++)
        if(b[i][j]-b[i-l][j]-b[i][j-l]+b[i-l][j-l]==l*l)
          ans=l;
  cout<<ans;
}