1 条题解
-
0
考虑逆向思维。
每次染一个 的,那么最后必然会有一个 的矩形,我们令这个矩形最后染色,继续向前推,把后面染色的都标记为零就做完了。
代码
#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
- 上传者