CF432E Square Tiling(贪心)

不难想到贪心和一个错误的贪心思路:判断当前应该填充哪个字母,用它填充一个尽可能大的正方形,向下递归。

我们将会得到 CF432E Square Tiling(贪心) 的好成绩。为什么呢?对比一下 Codeforces 给出的样例:

Output	Answer
//……以上部分相同
BBBBB	BBBBB
AAACC	AAACA
AAACC	AAABB
AAABA	AAABB

直接填充一个 \(2\times 2\) 的 C 正方形,使得后面本可以填 A B 的位置被浪费了。

本可以?也就是说,在样例给出部分第 \(2\) 行第 \(5\) 列的位置,根据已经填好的字母,应该填 A 而不是 C,我们第一个贪心思路是毫无道理的。不能一次性刷一个正方形,而要一个一个判断是否是最优

下面是查询最优字母的函数:

inline char get(int x, int y) {
	if (a[x][y]) return a[x][y];
	int i;
	for (i = 1; i <= 26; ++i)
		if (a[x - 1][y] != i && a[x + 1][y] != i && 
			a[x][y - 1] != i && a[x][y + 1] != i)
			return i;
}

下面是主函数核心部分代码:

for (x = 1; x <= n; ++x) {
	for (y = 1; y <= m; ++y) {
		if (a[x][y]) continue;
		col = get(x, y);
		k = 0;
		while (get(x, y + k) == col && x + k <= n && y + k <= m)
			++k;
		/*cerr << k << endl;*/
		for (i = x; i < x + k; ++i)
			for (j = y; j < y + k; ++j)
				a[i][j] = col;
	}
}

THE END

上一篇:请定义一个square_of_sum()函数,它接收一个list,返回list中每个元素平方的和。


下一篇:[LeetCode] 778. Swim in Rising Water