题目大意

给定一个大小为 $n\times m$ 的画板，初始画板上没有任何颜色，每次可以选择一个 $2\times 2$ 的相邻田字格进行颜色填充。给定画板的最终形态，判断是否可以绘制出这样的形态，如果可以，给出任意一种可行的绘制方案。

解题思路

采取倒推的解题策略，先找出最后一步填充的田字格。
把所有可选田字格扫描一遍，找出颜色相同的田字格，并将其设为答案序列的最后几步。
接着把已加入答案序列的田字格替换成特殊标记。
每当确定一个田字格加入答案序列时，判断它周围的田字格，是否也是全为一种颜色的，他周围的田字格最多只有 $9$ 种，找到可行的，就加入答案序列。
最后，判断画板上是否全是特殊标记，如果还有普通颜色，那么即为无法达到。
时间复杂度 $\Theta(nm)$。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1001][1001];
struct Answer{
	int x,y,col;
}ans[1000001];//答案序列
int anslen;
bool p[1001][1001];//标记
inline void work(int x,int y){
	if(x<1||x>n-1||y<1||y>m-1||p[x][y])return;
	bool flag=true; int col=-1;
	for(int i=0;i<=1;i++)
		for(int j=0;j<=1;j++){
			if(a[x+i][y+j]==-1)continue;
			if(col==-1)col=a[x+i][y+j];
			flag&=a[x+i][y+j]==col;
		}
	if(col==-1)return;
	if(flag)ans[++anslen]={x,y,col},p[x][y]=true;
}
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++)work(i,j);//判断是否是2*2的同色田字格，是的话加入答案
	for(int i=1;i<=anslen;i++){
		for(int j=0;j<=1;j++)
			for(int jj=0;jj<=1;jj++)
				a[ans[i].x+j][ans[i].y+jj]=-1;//标记
		for(int j=-1;j<=1;j++)
			for(int jj=-1;jj<=1;jj++)
				work(ans[i].x+j,ans[i].y+jj);
	}
	bool flag=true;
	for(int i=1;i<=n&&flag;i++)
		for(int j=1;j<=m&&flag;j++)
			flag=a[i][j]==-1;
	if(!flag)printf("-1\n");//还有没绘制的田字格
	else{
		printf("%d\n",anslen);
		for(int i=anslen;i>=1;i--)
			printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].col);
	}
	return 0;
} 

考虑需要确定染色的顺序。
发现所有 $2 \times 2$ 相同的都可以最后染色，染完之后把它设置为通配符（这之前无论是什么都行，因为会被覆盖）。然后就是一个类似拓扑排序过程的 bfs 。

启发：确定过程 --> 逐步确定最后一个（最先一个），也是拓扑排序的思想。

const int maxn = 1e3 + 10;
int a[maxn][maxn];
pair<bool,int> check(int x, int y) {
    int t = 0;
    rep(i,x,x+1) rep(j,y,y+1) if(a[i][j]) t = a[i][j];
    rep(i,x,x+1) rep(j,y,y+1) if(a[i][j] && t != a[i][j]) return {false, t};
    return {true, t};
}
bool empty(int x, int y) {
    rep(i,x,x+1) rep(j,y,y+1) if(a[i][j]) return false;
    return true;
}
void reset(int x, int y) {
    rep(i,x,x+1) rep(j,y,y+1) a[i][j] = 0;
}

struct pt { int x, y; };
queue< pt > q;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    rep(i,1,n) rep(j,1,m) scanf("%d", &a[i][j]);
    rep(i,1,n-1) rep(j,1,m-1)
        if(check(i, j).first)
            q.push({i, j});

    vector< pair<pt, int> > ans;
    while(!q.empty()) {
        pt cur = q.front(); q.pop();
        if(empty(cur.x, cur.y)) continue;
        ans.push_back({cur, check(cur.x, cur.y).second});
        reset(cur.x, cur.y);
        rep(i,max(1, cur.x - 1), min(cur.x + 1, n - 1))
            rep(j,max(1, cur.y - 1), min(cur.y + 1, m - 1))
            if(!empty(i, j) && check(i, j).first)
                q.push({i, j});
    }
    rep(i,1,n) rep(j,1,m) if(a[i][j]) {
        puts("-1"); return 0;
    }
    printf("%zu\n", ans.size());
    for(auto it = ans.rbegin(); it != ans.rend(); ++ it) {
        printf("%d %d %d\n", it -> first.x, it -> first.y, it -> second);
    }
    return 0;
}