题解 | #E 01矩阵#

#题意

一个n行n列的01矩阵中，每行的和组成一个长度为n的排列，列也是如此，并且0与1的连通块个数之和为n。

关键词

构造，找规律

题解

首先每行的1的个数一个从0到n-1递增，列也如此。

0000
0001
0011
0111

00000
00001
00011
00111
01111

但是我们还要考虑连通块的个数问题，所以要把0与0用1隔开，将1组成的连通块看成一个隔离带。 观察发现1组成的连通块可以看出一个个倒L形状的隔离带，就比如；

1

 1
11

  1
  1
111

因此找到一下规律

00
01

000
011
010

0000
0111
0100
0101

00000
01111
01000
01011
01010

#include<bits/stdc++.h>
using namespace std;
int arr[1005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j&&i%2==0){
                cout<<"1";
                arr[i]=1;
            }
            else if(arr[i]||arr[j]) cout<<"1";
            else cout<<"0";
        }
        cout<<endl;
    }
}