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

#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;
}