题解：CF1638D Big Brush

jess1ca1o0g3 · 2025-09-07 22:39:28 · 题解

由于每个操作会覆盖一个块，所以最后一定会有一个完整的块。从这个块开始搜索，将它还原，枚举与其八连通的块。如果这个块的颜色一样（即只有空白 0 和一种颜色，但不能全白），说明这一层可以把这个块还原，递归下去。如果最后无法让整个画布变白，说明无解。这样做每次至少会还原一个点，最差便是 nm 次操作，符合题意。

代码如下：

#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c,d) for(int a=b;a<=c;a+=d)
#define R(a,b,c,d) for(int a=b;a>=c;a-=d)

using namespace std;
const int N=1e3+5;

void solve();
int n,m,a[N][N],ans[N*N][3],cnt,dx[9]={0,0,0,1,-1,1,-1,1,-1},dy[9]={0,1,-1,0,0,1,1,-1,-1};

signed main(){
  int Test=1;
//  scanf("%d",&Test);
  while(Test--) solve();
  return 0;
}

void dfs(int x,int y,int z){
  if(!z) return;
  ans[++cnt][0]=x;
  ans[cnt][1]=y;
  ans[cnt][2]=z;
  a[x][y]=a[x+1][y]=a[x][y+1]=a[x+1][y+1]=0;
  L(i,1,8,1){
    int xx=x+dx[i],yy=y+dy[i];
    if(xx<1||xx>n-1||yy<1||yy>m-1) continue;
    int zz=max({a[xx][yy],a[xx+1][yy],a[xx][yy+1],a[xx+1][yy+1]});
    if(zz>0&&(!a[xx][yy]||a[xx][yy]==zz)&&(!a[xx+1][yy]||a[xx+1][yy]==zz)&&(!a[xx][yy+1]||a[xx][yy+1]==zz)&&(!a[xx+1][yy+1]||a[xx+1][yy+1]==zz)) dfs(xx,yy,zz);
  }
}

void solve(){
  scanf("%d%d",&n,&m);
  L(i,1,n,1){
    L(j,1,m,1) scanf("%d",&a[i][j]);
  }
  L(i,1,n-1,1){
    L(j,1,m-1,1){
      if(a[i][j]==a[i+1][j]&&a[i+1][j]==a[i][j+1]&&a[i][j+1]==a[i+1][j+1]) dfs(i,j,a[i][j]);
    }
  }
  L(i,1,n,1){
    L(j,1,m,1){
      if(a[i][j]){
        printf("-1\n");
        return;
      }
    }
  }
  printf("%d\n",cnt);
  R(i,cnt,1,1) printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
}