题目简单描述：找到给定矩形中，最大的，只有对角线为1的正方形。
既然又是从矩形找正方形，于是又想故技重施使用悬线法，预处理每个值为1的点到周围最多能拓展几个值为0的点。不过之后发现这样做还是很暴力，每次只能从左上（右上）转移，想着当时暴力判断能否转移。
但是其实没必要这么做，而且这样复杂度也比较高。正解的确预处理了每个点能拓展的距离，不过下面就不用了（因为你是从上向下走的），之后还是老套路，只能从左上（右上）三个点转移过来，不过这次左上（右上）是实际的dp值，其他方向都是事先预处理好的最大能拓展为0的长度。
这个取最小和上一道题是同理的，都要满足约束条件。之后这个题就很愉快的完成了。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 2505; const int INF = 1000000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,m,l[M][M],u[M][M],dp[M][M],ans; bool g[M][M]; int main() { n = read(),m = read(); rep(i,1,n) rep(j,1,m) { g[i][j] = read(); if(!g[i][j]) l[i][j] = l[i][j-1] + 1,u[i][j] = u[i-1][j] + 1; else dp[i][j] = min(dp[i-1][j-1],min(l[i][j-1],u[i-1][j])) + 1; ans = max(ans,dp[i][j]); } memset(dp,0,sizeof(dp)); memset(l,0,sizeof(l)); rep(i,1,n) per(j,m,1) { if(!g[i][j]) l[i][j] = l[i][j+1] + 1; else dp[i][j] = min(dp[i-1][j+1],min(l[i][j+1],u[i-1][j])) + 1; ans = max(ans,dp[i][j]); } printf("%d ",ans); return 0; }