自动搬运

查看原文

来自洛谷，原作者为

	芜湖起飞 1017

搬运于2025-08-24 21:34:01，当前版本为作者最后更新于2020-10-13 16:32:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好体验（大概

看完题第一反应：我明白了（并没有

错误思路：能放颜色的放下去，然后尽量拓展，然后做下一个点,纯模拟

快乐敲完，样例一输，过了

网站一交，WA了

努力想了想

在$N<M$的时候这种贪心并不正确

例： $N=3,M=5$时

错误解法答案：

AAABB

AAABB

AAACA

正解：

AAABA

AAACB

AAABA

所以要改变思路，将原来的“能拓展就拓展”改为“判断下一个点能不能放比当前小的颜色，若不能则继续拓展，反之退出拓展”

来看代码——

//:D
#include<bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 1, 0, 0}, dy[4]={0, 0, 1, -1};

int n, m;
int a[505][505];

bool dif(int k, int x, int y) {//点(x, y)能否放入颜色k 
	if (x > n || y > m) return 0;//越界 
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (a[nx][ny] == k) return 0;//点(x,y)四周有跟颜色k相同的 
	}
	return 1;
}

bool judge(int k, int x, int y) {
	int nx = x, ny = y;//这块瓷砖初始位置在(x,y)，最后右下角会在(x+nx-1,y+ny-1)，看下面代码理解就好了qwq 
	bool f = 0;//是否成功拓展 
	for (int i = 1; i <= n ; i++)
		if (a[nx][y] == -1 && a[x][ny] == -1 &&//没填色..
			dif(k, nx, y)  && dif(k, x, ny)) {//..并且颜色k可以填在(nx,y)与(x,ny)这两个点 
			int s = -1;
			for (int j = 0; j < k; j++)//枚举每一个小于k的颜色 
				if (dif(j, x, ny)) {//如果(x,ny)可以填这个颜色 
					s = j;//打个标记 
					break;
				}
			if (s != -1)break;//右边能填更优的颜色，停止拓展 
			f = 1;//上面没break说明已经成功拓展了
			nx++, ny++;//做下一个 
		}
		else break;
	for (int i = x; i < nx; i++)
		for (int j = y; j < ny; j++)
			a[i][j] = k;//全部染成这个颜色 
	return f;
}

int main(){
	memset(a,-1,sizeof(a));//a数组值0表示A，1表示B，以此类推，-1表示还没有颜色
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)//枚举每一个点 
			if (a[i][j] == -1)//如果还妹填色 
				for (int k=0 ; k<=25; k++)//枚举要填的颜色 
					if (judge(k, i, j)) break;//judge == 1说明填好了，break去做下一个没填色的点 

	//愉快输出—— 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			printf("%c", (char)'A' + a[i][j]);
		printf("\n");
	}
	return 0;
}

后记：

码风垃圾多多包涵

另外，这道题的答案只会用到ABCD四种颜色，大概是四色定理

完结撒花