巨大的牛棚

题目描述

给定一个 $N \times N$ 网格和 $T$ 个有树格子的坐标，求能建在空地上的正方形牛棚的最大边长。 $1 \le N \le 1000$ ， $1 \le T \le 10000$ 。

思路

设 $dp[r][c]$ 为以 $(r,c)$ 为右下角的全空正方形最大边长。若该格有树则 $dp[r][c]=0$ ；否则它由上方、左方、左上方三个相邻正方形共同决定，转移式为 $dp[r][c]=\min(dp[r-1][c],dp[r][c-1],dp[r-1][c-1])+1$ 。遍历网格取最大值即可。

参考代码

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#!/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 07:46
# update_at: 2026-10-01 07:46

import sys

def max_barn_side(n: int, trees: set[tuple[int, int]]) -> int:
    """全空最大正方形的边长：dp[r][c] = 以 (r, c) 为右下角的最大空正方形边长。"""
    best = 0
    row = [0] * (n + 1)  # 上一行 dp，虚拟第 0 行全 0；第 0 列哨兵也是 0，避免 c=1 时越界
    for r in range(1, n + 1):
        cur = [0] * (n + 1)
        for c in range(1, n + 1):
            if (r, c) in trees:  # 有树：以它为右下角的正方形不存在
                cur[c] = 0
            else:
                cur[c] = min(row[c], row[c - 1], cur[c - 1]) + 1
        best = max(best, max(cur))
        row = cur
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, t = next(data), next(data)
    trees = {(next(data), next(data)) for _ in range(t)}
    print(max_barn_side(n, trees))


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/**
 * 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:43
 * update_at: 2026-10-06 10:44
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005; // N <= 1000，多留一点

int dp[MAXN][MAXN];   // dp[r][c] 表示以 (r,c) 为右下角的全空正方形最大边长
bool tree[MAXN][MAXN]; // tree[r][c] 为 true 表示该格有树

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, t;
    cin >> n >> t;

    // 读入有树的坐标
    for (int i = 1; i <= t; i++) {
        int r, c;
        cin >> r >> c;
        tree[r][c] = true;
    }

    int ans = 0;
    // 按行递推每个格子的最大正方形边长
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= n; c++) {
            if (tree[r][c]) {
                dp[r][c] = 0; // 有树则不能作为正方形右下角
            } else {
                // 上方、左方、左上三者的最小值加一
                int up = dp[r - 1][c];
                int left = dp[r][c - 1];
                int ul = dp[r - 1][c - 1];
                dp[r][c] = min(up, min(left, ul)) + 1;
                if (dp[r][c] > ans) {
                    ans = dp[r][c];
                }
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

目录

题目描述

思路

参考代码