1 条题解

  • 0
    @ 2022-2-23 7:10:41

    考虑逆向思维。

    每次染一个 2×22\times 2 的,那么最后必然会有一个 2×22\times 2 的矩形,我们令这个矩形最后染色,继续向前推,把后面染色的都标记为零就做完了。


    代码
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1005;
    typedef pair<int,int> Int;
    queue<Int> q;
    pair<Int,int> ans[N*N];
    int a[N][N],n,m,tot;
    int check(int x,int y){
    	int ff=0;
    	for(int i=x;i<=x+1;i++)for(int j=y;j<=y+1;j++)
    		if(a[i][j]){
    			if(ff!=a[i][j]&&ff)return 0;
    			else ff=a[i][j];
    			
    		}
    	return ff;
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    	for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(check(i,j))q.push(make_pair(i,j));
    	while(!q.empty()){
    		auto p=q.front();
    		q.pop();
    		int x=p.first,y=p.second;
    		int ff=1;
    		for(int i=x;i<=x+1;i++)for(int j=y;j<=y+1;j++)if(a[i][j])ff=0;
    		if(ff)continue;
    		ans[++tot]=make_pair(make_pair(x,y),check(x,y));
    		a[x][y]=a[x+1][y]=a[x][y+1]=a[x+1][y+1]=0;
    		for(int i=x-1;i<=x+1;i++)for(int j=y-1;j<=y+1;j++)if(i>=1&&i<n&&j>=1&&j<m&&check(i,j))q.push(make_pair(i,j));
    	}
    	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j])return puts("-1"),0;
    	printf("%d\n",tot);
    	for(int i=tot;i;i--)printf("%d %d %d\n",ans[i].first.first,ans[i].first.second,ans[i].second);
    }
    
    • 1

    信息

    ID
    76
    时间
    3000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者