题解：P11476 [COCI 2024/2025 #3] 涂矩阵 / Bojanje

Emplace · 2025-04-23 15:33:23 · 题解

思路

此题如果直接硬构造，肯定非常困难，那不妨另辟蹊径。

我们显然可以在目标矩阵中发现一些完整的行和列，那么这些绝对是最后再整个涂。因为是最后整个涂，那我们直接孤立无视它，再看其它的。那看的时候跟前面一个道理（如果你找不到，那就是无解）。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[3000][3000],col[3000][3000],ans[3000][4],sum;
int cnt[3][3][3000]; 
int check(int type,int id){
 //   cout<<cnt[0][type][id]<<" "<<cnt[1][type][id]<<" "<<cnt[2][type][id]<<endl;
    if(cnt[0][type][id]){
        return 0;
    } 
    if(cnt[1][type][id]&&cnt[2][type][id]){
        return 0;
    } 
    if(cnt[1][type][id]){
        return 1;
    }
    if(cnt[2][type][id]){
        return 2;
    }
    return 0;
}
void pain_t(int colour,int i,int j){
    if(col[i][j]) return ;
    col[i][j]=colour;
    cnt[colour][1][i]--;
    cnt[colour][2][j]--;
}
void paint(int colour,int type,int id,int ZhiYang_in_Jiujiang){
    //cout<<colour<<" "<<type<<" "<<id<<" "<<ZhiYang_in_Jiujiang<<endl;
    ans[++sum][1]=type,ans[sum][2]=id,ans[sum][3]=colour;
    for(int i=1;i<=n;i++){
        if(type==1) pain_t(colour,id,i);
        if(type==2) pain_t(colour,i,id);
    } 
//  cout<<cnt[0][2][2]<<endl;
    for(int i=1;i<=n;i++){
    //  cout<<((type-1)^1+1)<<" "<<i<<endl;
        if(check((((type-1)^1)+1),i)) paint(check(((type-1)^1)+1,i),((type-1)^1)+1,i,id);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            cnt[a[i][j]][1][i]++;
            cnt[a[i][j]][2][j]++;
        }
    }
    //cout<<cnt[1][2][2]<<endl;
    for(int i=1;i<=n;i++){
        if(check(1,i)) /*cout<<1<<" "<<i<<endl,*/paint(check(1,i),1,i,114);
        if(check(2,i)) paint(check(2,i),2,i,114);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
//          cout<<col[i][j]<<" ";
            if(!col[i][j]&&a[i][j]){
                cout<<-1;
                return 0;
            }
        }
    //  cout<<endl;
    }
    cout<<sum<<endl;
    for(int i=sum;i>=1;i--){
        cout<<ans[i][1]<<" "<<ans[i][2]<<" "<<ans[i][3]<<endl;
    }
    return 0;
}