Luogu P2733 家的范围

YorkWu

March 14, 2019

1229 views

No comments

664 words

OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P2733 "题目链接")

#### 题目大意

给定一个$n\\times n$的01矩阵，问其中所有由1组成的边长不同的正方形的数量。

#### 输入

6
    101111
    001111
    111111
    001111
    101101
    111001

#### 输出

2 10
    3 4
    4 1

* * *

原来曾经做过一道题，用两个数组分别表示从一个点$(i,j)$向上、左走分别到达的第一个零的位置，这道题也能用。 - $l\[i\]\[j\]$表示从$(i,j)$点开始向左走，最长的1序列的长度。 - 同理，$u\[i\]\[j\]$表示从$(i,j)$点开始向上走，最长的1序列的长度。 - 理论复杂度$O(n^3)$ 详细解释看代码：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    int f[259],l[259][259],u[259][259],n;
    bool a[259][259];
    
    int main(){
        cin>>n;
        string s;
        for(int i=1;i<=n;i++){
            cin>>s;
            for(int j=1;j<=n;j++){
                a[i][j]=s[j-1]-'0';
                if(a[i][j]) l[i][j]=u[i][j]=1;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(a[i][j]) l[i][j]=max(l[i][j-1]+1,l[i][j]);//预处理l，u数组
                if(a[i][j]) u[i][j]=max(u[i-1][j]+1,u[i][j]);
            }
        }
    
        int minx=0x3f3f3f3f,maxx=0,maxn=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                minx=0x3f3f3f3f;
                maxx=0;//maxx代表以（i，j）作为右下角的最大正方形的边长。
                for(int k=i;i-k<u[i][j];k--){
                    minx=min(minx,l[k][j]);//将minx更新为当前第k行至第i行最大矩阵的长。
                    if(min(minx,u[i][j])>=2&&(i-k+1<=min(minx,u[i][j]))) maxx=max(maxx,i-k+1);
                    //如果当前边长大于二，并且当前宽小于等于长，就让maxx更新为最长边长的正方形。
                }
                f[maxx]++;//以(i,j)为右下角的最大正方形的边长加一。
                maxn=max(maxx,maxn);
            }
        }
        int t=0;
        for(int i=maxn;i>1;i--){
            f[i-1]+=f[i];//因为如果容纳一个边长为x的正方形，那一定可以容纳边长比i小的正方形。
        }
        for(int i=2;i<=n;i++){
            if(f[i]) cout<<i<<" "<<f[i]<<endl;
        }
        return 0;
    }
```

Last modification：March 14, 2020