<题目链接>
题目大意：
给你一个由01组成的矩形，现在问你，该矩形中，最多只含一个1的正方形的边长最长是多少。
解题分析：
用二维前缀和维护一下矩形的01值，便于后面直接$O(1)$查询任意子矩阵中1的个数，然后就是二分答案枚举边长。
#include <bits/stdc++.h>
using namespace std; template<typename T>
inline void read(T&x){
x=;int f=;char ch = getchar();
while(ch<'' ||ch>''){ if(ch=='-')f=-;ch=getchar(); }
while(ch>='' && ch<=''){ x=x*+ch-''; ch=getchar(); }
x*=f;
}
#define rep(i,s,t) for(int i=s;i<=t;i++)
const int N = 1e3+;
int n,m,arr[N][N],sum[N][N]; bool check(int x){
rep(i,,n) rep(j,,m) {
if(i<x || j<x)continue;
int num=sum[i][j]-sum[i][j-x]-sum[i-x][j]+sum[i-x][j-x]; //得到任意子矩阵的值
if(num<=)return true;
}
return false;
}
int main(){
int T;read(T);while(T--){
memset(arr,,sizeof(arr));
memset(sum,,sizeof(sum));
read(n);read(m);
rep(i,,n) rep(j,,m) {
read(arr[i][j]);
sum[i][j] = arr[i][j]+sum[i-][j]+sum[i][j-]-sum[i-][j-]; //维护二维前缀和
}
int l=,r=1e3+,ans=;
while(l<=r){ //二分枚举正方形边长
int mid=l+r>>;
if(check(mid))ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
}
}