家的范围

题目描述

给定一个 $N\times N$ （ $2\leqslant N\leqslant 250$ ）的 0/1 字符矩阵，1 表示完好、0 表示被毁坏。求所有边长 $k\geqslant 2$ 、内部不含 0 的正方形子区域个数（可重叠），按 $k$ 从小到大输出每个确实存在的尺寸及个数。

输入：第一行 $N$ ，接下来 $N$ 行每行 $N$ 个无空格字符。样例输入 6 / 101111 / 001111 / 111111 / 001111 / 101101 / 111001，输出 2 10 / 3 4 / 4 1。

思路

设 $f[r][c]$ 为以 $(r,c)$ 为右下角的最大全 1 正方形边长，格子为 0 时 $f=0$ ，否则 $f[r][c]=\min(f[r-1][c-1],f[r-1][c],f[r][c-1])+1$ 。若 $f[r][c]=L$ ，该格向边长 $1\sim L$ 的尺寸各贡献一个正方形；按 $L$ 分桶后从大到小做一遍后缀和，即得每个存在尺寸的总数。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 05:19
# update_at: 2026-10-04 11:18

import sys
from collections import Counter


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    grid = [next(data).decode() for _ in range(n)]

    # f[r][c] = 以 (r, c) 为右下角的最大全 1 正方形边长；
    # 全部以 k 结尾的正方形套住了以 k-1 结尾的较小正方形，按边长分桶即可。
    f = [[0] * n for _ in range(n)]
    sizes = Counter()
    for r in range(n):
        for c in range(n):
            if grid[r][c] == '1':
                top_left = f[r - 1][c - 1] if r and c else 0
                f[r][c] = min(top_left, f[r - 1][c], f[r][c - 1]) + 1
                sizes[f[r][c]] += 1

    # 边长为 k 的正方形个数 = sum(cnt[j] for j >= k)，从大到小做一次后缀和
    count = [0] * (n + 1)
    total = 0
    for k in range(n, 1, -1):
        total += sizes[k]
        if total:
            count[k] = total
    out = [f'{k} {count[k]}' for k in range(2, n + 1) if count[k]]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:28
 * update_at: 2026-10-06 10:28
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 255;
int n;                       // 牧场边长
char grid[MAXN][MAXN];       // 输入网格，'1' 表示完好，'0' 表示毁坏
int f[MAXN][MAXN];           // f[r][c] = 以 (r,c) 为右下角的最大全 1 正方形边长
int sizes[MAXN];             // sizes[k] = 恰好以边长 k 结尾的格子个数
int cnt[MAXN];               // cnt[k] = 边长为 k 的全 1 正方形总数

int main() {
    scanf("%d", &n);
    for (int r = 1; r <= n; r++) {
        scanf("%s", grid[r] + 1);
    }

    // 逐格递推最大全 1 正方形：min(上、左、左上) + 1
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= n; c++) {
            if (grid[r][c] != '1') {
                continue;
            }
            int up = f[r - 1][c];
            int left = f[r][c - 1];
            int up_left = f[r - 1][c - 1];
            int best = up < left ? up : left;
            if (up_left < best) {
                best = up_left;
            }
            f[r][c] = best + 1;
            sizes[f[r][c]]++;
        }
    }

    // 边长为 k 的正方形总数 = 所有 f >= k 的格子数，从大到小做后缀和
    int total = 0;
    for (int k = n; k >= 2; k--) {
        total += sizes[k];
        cnt[k] = total;
    }

    // 只输出确实存在的尺寸
    for (int k = 2; k <= n; k++) {
        if (cnt[k] > 0) {
            printf("%d %d\n", k, cnt[k]);
        }
    }
    return 0;
}

目录

题目描述

思路

参考代码