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