# 悬线法(Hanging line method)-其他

## 悬线法(Hanging line method)

01矩阵求最大全1的矩形和正方形

``````#include<bits/stdc++.h>
using namespace std;
const int N = 2020;
int l[N][N],r[N][N],u[N][N];
bool a[N][N];
int main(){
int n,m;    cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j){
cin >> a[i][j];

l[i][j] = r[i][j] = j;
u[i][j] = 1;
}

for(int i = 1; i <= n; ++i)
for(int j = 2; j <= m; ++j)
if(a[i][j] != a[i][j-1])
l[i][j] = l[i][j-1];
for(int i = 1; i <= n; ++i)
for(int j = m - 1; j ; --j)
if(a[i][j] != a[i][j + 1])
r[i][j] =r[i][j + 1];
int ans1 = 1,ans2 = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j){
if(i != 1 && a[i][j] != a[i-1][j]){
u[i][j] = u[i-1][j] + 1;
l[i][j] = max(l[i][j],l[i-1][j]);
r[i][j] = min(r[i][j],r[i-1][j]);
}

ans1 = max(ans1,min(u[i][j],r[i][j] - l[i][j] + 1));
ans2 = max(ans2,(r[i][j] - l[i][j] + 1) * u[i][j]);
}
cout << ans1 * ans1 << '\n' << ans2 << '\n';

return 0;
}``````
————————

01 matrix to find the rectangle and square with the largest total 1

``````#include<bits/stdc++.h>
using namespace std;
const int N = 2020;
int l[N][N],r[N][N],u[N][N];
bool a[N][N];
int main(){
int n,m;    cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j){
cin >> a[i][j];

l[i][j] = r[i][j] = j;
u[i][j] = 1;
}

for(int i = 1; i <= n; ++i)
for(int j = 2; j <= m; ++j)
if(a[i][j] != a[i][j-1])
l[i][j] = l[i][j-1];
for(int i = 1; i <= n; ++i)
for(int j = m - 1; j ; --j)
if(a[i][j] != a[i][j + 1])
r[i][j] =r[i][j + 1];
int ans1 = 1,ans2 = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j){
if(i != 1 && a[i][j] != a[i-1][j]){
u[i][j] = u[i-1][j] + 1;
l[i][j] = max(l[i][j],l[i-1][j]);
r[i][j] = min(r[i][j],r[i-1][j]);
}

ans1 = max(ans1,min(u[i][j],r[i][j] - l[i][j] + 1));
ans2 = max(ans2,(r[i][j] - l[i][j] + 1) * u[i][j]);
}
cout << ans1 * ans1 << '\n' << ans2 << '\n';

return 0;
}``````