题解：洛谷 P2701 [USACO5.3] 巨大的牛棚 Big Barn

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P2701 [USACO5.3] 巨大的牛棚 Big Barn

【题目描述】

FJ 有一个大小为n × n n\times nn×n的农场（1 ≤ n ≤ 1000 1\le n\le 10001≤n≤1000），他想要在他的农场上建造一座正方形大牛棚。他的农场中有t tt棵果树（1 ≤ t ≤ 10000 1\le t\le100001≤t≤10000），但他为了不破坏果树，就想找一个空旷无树的地方修建牛棚。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚的边长。当然，牛棚的边必须和水平轴和垂直轴平行。

考虑下面的农场，.表示没有树的方格，#表示有树的方格。

0 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # . . . # . . 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . . 6 . . # . . . . . 7 . . . . . . . . 8 . . . . . . . .

最大的牛棚是边长为5 55的，可以建造在农场右下角的两个位置其中一个。

【输入】

第1 11行输入两个正整数n nn和t tt。

第2 ∼ t + 1 2\sim t+12∼t+1行输入两个正整数x , y ( 1 ≤ x , y ≤ n ) x,y\ (1\le x,y\le n)x,y(1≤x,y≤n)。

【输出】

只由一行组成，约翰的牛棚的最大边长。

【输入样例】

8 3 2 2 2 6 6 3

【输出样例】

5

【核心思想】

1. 问题分析：给定n × n n \times nn×n的网格，其中有t tt个位置有树（障碍物），求边与坐标轴平行的最大正方形空区域（不含树）的边长。这是一个二维 DP问题，关键在于状态设计能递推地利用子问题的最优解。

2. 算法选择：

   • 二维动态规划：设d p [ i ] [ j ] dp[i][j]dp[i][j]表示以( i , j ) (i, j)(i,j)为右下角的最大无树正方形边长
   • 状态转移：当前位置能扩展的正方形边长受限于上方、左方、左上方三个相邻位置的最小值

3. 关键步骤：

   • 初始化：读取n nn（农场边长）、t tt（果树数量），标记有树的位置g [ x ] [ y ] = 1 g[x][y] = 1g[x][y]=1
   • DP 数组初始化：d p [ i ] [ j ] dp[i][j]dp[i][j]初始化为较大值（边界处理），a n s = 0 ans = 0ans=0
   • 递推计算（遍历i ii从1 11到n nn，j jj从1 11到n nn）：
     • 若g [ i ] [ j ] = 1 g[i][j] = 1g[i][j]=1（有树）：d p [ i ] [ j ] = 0 dp[i][j] = 0dp[i][j]=0
     • 若i = 1 i = 1i=1或j = 1 j = 1j=1（边界）：d p [ i ] [ j ] = 1 dp[i][j] = 1dp[i][j]=1（无树位置）
     • 否则：状态转移d p [ i ] [ j ] = min ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] ) + 1 dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1dp[i][j]=min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1
     • 更新全局答案a n s = max ⁡ ( a n s , d p [ i ] [ j ] ) ans = \max(ans, dp[i][j])ans=max(ans,dp[i][j])
   • 输出答案a n s ansans

4. 时间/空间复杂度：

   • 时间复杂度：O ( n 2 ) O(n^2)O(n2)，双层循环遍历整个网格
   • 空间复杂度：O ( n 2 ) O(n^2)O(n2)，d p dpdp二维数组和g gg标记数组

5. 二维 DP 的核心思想：

   • 子结构重叠：以( i , j ) (i, j)(i,j)为右下角的正方形，其边长受限于三个方向（上、左、左上）能形成的最小正方形，因为这三个方向必须同时满足无树才能扩展
   • 最小值约束：d p [ i ] [ j ] dp[i][j]dp[i][j]取三者最小值加1 11，因为只要任一方向存在树或边界限制，当前正方形就无法突破该限制
   • 边界处理：第一行和第一列的无树位置最大只能形成1 × 1 1 \times 11×1的正方形，作为递推基础
   • 贪心最优性：每个位置记录以它为右下角的最大正方形，全局取最大即得答案
   • 适用于最大正方形/矩形、矩阵覆盖、障碍物规避类问题

【算法标签】

#普及 #线性DP-二维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 最大农场尺寸intn,t,ans;// n:农场边长, t:果树数量, ans:最大正方形牛棚边长intg[N][N];// g[i][j]:标记该位置是否有树（1表示有树，0表示无树）intdp[N][N];// dp[i][j]:以(i,j)为右下角的最大无树正方形边长intmain(){cin>>n>>t;// 读入农场边长和果树数量for(inti=1;i<=t;i++)// 读入每棵果树的位置{intx,y;cin>>x>>y;g[x][y]=1;// 标记该位置有树}// 初始化dp数组为较大值（用于边界处理）memset(dp,0x3f,sizeof(dp));for(inti=1;i<=n;i++)// 外层循环：枚举行for(intj=1;j<=n;j++)// 内层循环：枚举列{if(g[i][j])// 如果当前位置有树{dp[i][j]=0;// 以该位置为右下角的正方形边长为0（不能建牛棚）}elseif(i==1||j==1)// 边界位置（第一行或第一列）dp[i][j]=1;// 边界上无树的位置最大正方形边长为1else{// 状态转移：以(i,j)为右下角的最大正方形边长// 取决于上方、左方、左上方三个位置的最小值加1// 原理：如果这三个方向都能形成边长为k的正方形，则当前可形成边长为k+1的正方形dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;}ans=max(ans,dp[i][j]);// 更新全局最大边长}cout<<ans<<endl;// 输出最大正方形牛棚的边长return0;}

【运行结果】

8 3 2 2 2 6 6 3 5