P1681 最大正方形II【洛谷算法习题】

P1681 最大正方形II网页链接P1681 最大正方形II题目背景忙完了学校的事v 神终于可以做他的“正事”陪女朋友散步。一天他和女朋友走着走着不知不觉就来到了一个千里无烟的地方。v 神正要往回走如发现了一块牌子牌子上有一行小字和一张图小字说道“找到图上最大的交错正方形之后和我联系这块地就是你的了。”在房价疯长的年代v 神当然不愿错过这个机会于是开始找了起来……以 v 神的能力当然找不出来了你能帮 v 神找出来吗题目描述图上有一个矩阵由N × M N\times MN×M个格子组成这些格子由两种颜色构成黑色和白色。请找到面积最大的且内部是黑白交错即两个相连的正方形颜色不能相同的正方形。输入格式第一行两个整数N NN和M MM分别表示行数和列数。接下来有N NN行每行M MM个数0 00或1 11分别表示这个格子是黑色或白色。输出格式仅有一行表示满足条件最大正方形的边长。输入输出样例 #1输入 #13 3 0 1 0 1 0 0 1 1 1输出 #12说明/提示样例解释( 1 , 1 ) (1,1)(1,1)到( 2 , 2 ) (2,2)(2,2)这个正方形是满足条件的它的边长是2 22。数据范围及约定对于30 % 30\%30%的数据1 ≤ N , M ≤ 20 1\le N,M \le 201≤N,M≤20对于60 % 60\%60%的数据1 ≤ N , M ≤ 300 1\le N,M \le 3001≤N,M≤300对于100 % 100\%100%的数据1 ≤ N , M ≤ 1500 1\le N,M \le 15001≤N,M≤1500。解题思路本题是二维动态规划问题要求在一个由黑白两色组成的矩阵中找到面积最大的交错正方形。交错正方形内部相邻格子颜色必须不同即黑白交替。通过定义两种状态分别表示以当前格子为右下角且当前格子为黑色或白色的最大交错正方形边长利用三个方向的状态递推即可高效求解。1. 问题等价转化记a[i][j]为格子颜色0表示黑色1表示白色。需要找到一个最大的正方形区域满足区域内任意相邻上下左右格子颜色不同。根据黑白交替的性质实际上整个正方形内部的颜色分布是固定的对角线上颜色相同相邻格子颜色相反。对于以(i,j)为右下角且该格子颜色为0的最大交错正方形其左上角、上方和左方的格子颜色必须为1且它们所在的最大交错正方形边长也必须足够大。类似地颜色为1时对称。2. 动态规划状态设计定义dp[i][j][0]以(i,j)为右下角且a[i][j] 0的最大交错正方形边长。定义dp[i][j][1]以(i,j)为右下角且a[i][j] 1的最大交错正方形边长。初始时所有dp值为0。对于任意格子如果它本身颜色符合状态则至少可以形成边长为1的正方形。3. 状态转移方程若a[i][j] 0dp[i][j][0] min(dp[i-1][j][1], dp[i][j-1][1], dp[i-1][j-1][0]) 1解释要形成以(i,j)为右下角、颜色为0的交错正方形需要上方格子(i-1,j)能形成颜色为1的边长至少为dp[i][j][0]-1的交错正方形左方格子(i,j-1)能形成颜色为1的边长至少为dp[i][j][0]-1的交错正方形左上方格子(i-1,j-1)能形成颜色为0的边长至少为dp[i][j][0]-1的交错正方形保证对角线颜色一致。取三者的最小值再加1即得到当前最大边长。若a[i][j] 1dp[i][j][1] min(dp[i-1][j][0], dp[i][j-1][0], dp[i-1][j-1][1]) 1对称地上方和左方需颜色为0左上方需颜色为1。4. 算法流程读入矩阵大小n,m和颜色值。按行从左到右遍历每个格子根据当前格子颜色选择对应的状态转移。更新全局答案ans max(ans, dp[i][j][0/1])。输出最大边长ans。5. 复杂度分析时间复杂度双重循环遍历所有格子每个格子O ( 1 ) O(1)O(1)转移总复杂度O ( N M ) O(NM)O(NM)。N , M ≤ 1500 N,M \le 1500N,M≤1500计算量约2.25 × 10 6 2.25 \times 10^62.25×106非常快。空间复杂度需要存储原矩阵和 DP 数组O ( N M ) O(NM)O(NM)。由于状态转移只依赖上一行和当前行左方可优化为滚动数组但本题空间限制足够直接使用三维数组亦可。总结通过定义两种颜色状态利用交错正方形内部颜色分布的规律将问题转化为简单的最小值递推。DP 状态清晰转移方程体现了“上方、左方、左上方”三个方向的约束最终取全局最大值即可。该方法高效且易于实现是解决此类棋盘交错问题的典型方案。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll dp[1505][1505][2],a[1505][1505],n,m,ans;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(ll i1;in;i)for(ll j1;jm;j)cina[i][j];for(ll i1;in;i)for(ll j1;jm;j){if(a[i][j]0){dp[i][j][0]min(min(dp[i-1][j][1],dp[i][j-1][1]),dp[i-1][j-1][0])1;ansmax(ans,dp[i][j][0]);}if(a[i][j]1){dp[i][j][1]min(min(dp[i-1][j][0],dp[i][j-1][0]),dp[i-1][j-1][1])1;ansmax(ans,dp[i][j][1]);}}coutansendl;return0;}