打开英文网站字体不对,云南高端建设网站,手机网站程序源码,湖北住房建设网站正题 题目大意
一个N∗NN*NN∗N的01矩阵#xff0c;求一个面积最大的全为1的正方形 解题思路
先O(n2)O(n^2)O(n2)预处理hi,jh_{i,j}hi,j表示在(i,j)(i,j)(i,j)这个位置向右有多少个连续的1。然后二分边长。 时间复杂度:O(n2logn):O(n^2\ log\ n):O(n2 log n) codecodecode…正题 题目大意
一个N∗NN*NN∗N的01矩阵求一个面积最大的全为1的正方形 解题思路
先O(n2)O(n^2)O(n2)预处理hi,jh_{i,j}hi,j表示在(i,j)(i,j)(i,j)这个位置向右有多少个连续的1。然后二分边长。 时间复杂度:O(n2logn):O(n^2\ log\ n):O(n2 log n) codecodecode
#includecstdio
#includeiostream
#includealgorithm
using namespace std;
int n,h[1100][1100],l,r;
bool a[1100][1100];
bool check(int l)
{for(int j1;jn;j){int sum0;for(int i1;in;i){if(h[i][j]l) sum;else sum0;if(suml) return true;}}return false;
}
int main()
{scanf(%d,n);for(int i1;in;i)for(int j1;jn;j){char x;cinx;a[i][j]x-0;}for(int i1;in;i){int sum0;for(int jn;j1;j--){if(a[i][j]) sum;else sum0;h[i][j]sum;}}l1;rn;while(lr){int mid(lr)/2;if(check(mid)) lmid1;else rmid-1;}printf(%d,r*r);
}
