每日一题-21th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

LuoGu P1228. 地毯填补问题

题目描述

相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：

并且每一方格只能用一层地毯，迷宫的大小为 $2^k\times 2^k$ 的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以运行时间限制为 $1$ 秒。

说明

输入格式

输入文件共 $2$ 行。

第一行一个整数 $k$，即给定被填补迷宫的大小为 $2^k\times 2^k$（$0\lt k\leq 10$）；
第二行两个整数 $x,y$，即给出公主所在方格的坐标（$x$ 为行坐标，$y$ 为列坐标），$x$ 和 $y$ 之间有一个空格隔开。

输出格式

将迷宫填补完整的方案：每一补（行）为 $x y c$（$x,y$ 为毯子拐角的行坐标和列坐标，$c$ 为使用毯子的形状，具体见上面的图 $1$，毯子形状分别用 $1,2,3,4$ 表示，$x,y,c$ 之间用一个空格隔开）。

样例 1 输入

1
2

3                          
3 3

样例 1 输出

Special Judge 提示

spj 报错代码解释：

$c$ 越界；
$x,y$ 越界；
$(x,y)$ 位置已被覆盖；
$(x,y)$ 位置从未被覆盖。

思路

这题本人一开始真的一点思路都没有，因为我在想，这么多种填补方式，应该从哪里判断？我应该从哪里确定填补方式，使得“恰好剩余指定位置，并且铺满其他位置”呢？

转念一想，那么出题人怎么保证 区域大小、空缺位置这两者数据组合，一定能由以上 4 种地毯恰好覆盖？我发现区域大小上似乎有些 “蹊跷”：大小为 $2^k\times 2^k$，为什么一定是 2 的 k 次幂？为什么一定要是正方形的？

我自己给自己解释，首先因为地毯的结构如此，一块地毯至少需要占用 2 × 2 的空间，还剩余一个区域，比如 $k=1$ 时，从 1 ~ 4 号地毯中一定能找到一个，空缺正好是 “公主站立的位置”；

$k=2$ 时，思路就来了！4 × 4 的格子可不可以转化成 2 × 2 的格子进行处理呢？ 把 4 × 4 拆成 4 个区域的 2 × 2，那么 “公主位置” 必然存在于四个区域中的一个，这个小区域直接用 2 × 2 的方法必然能找到一块地毯铺满！那其他三个区域怎么用地毯填满？它们都是完整的 2 × 2 啊！ 有一个巧妙的思路是，把它们每一个都拆成缺一个位置的区域，如图：

总结一下：4 × 4 的问题（等价于 $k=2$ 问题）可以转化为 ① 存在 “公主” 的 2 × 2 问题（等价于 $k=1$ 问题），和 ② 不存在 “公主” 的 2 × 2 问题（通过各挖一块转化成 ①）。这样 $k=2$ 问题就转化为了 $k=1$ 问题；

至此，$k=1$ 和 $k=2$ 的问题已经全部解决；那么任意的 $k$ 呢？它又如何转化为 $k=2$、$k=1$ 的问题？

同理可知，对任意的 $k$ 问题可以转化为：① 存在公主的 $2^{k-1}\times2^{k-1}$ 问题（等价于 $n=k-1$ 的子问题），和 ② 不存在公主的 $2^{k-1}\times2^{k-1}$ 问题，一定可以通过 “平分为 4 个区域再加地毯” 的方式转化为 ①；如图：

到目前为止，这道题在思路上已经完成了，现在就差代码实施了；

实现

#include<cstdio>
using namespace std;

void solver(int startX, int endX, int startY, int endY, int pX, int pY) {
    if (endX - startX == 1) {    // 2 × 2
        if (startX == pX && startY == pY) printf("%d %d 1\n", endX, endY);
        else if (startX == pX && endY == pY) printf("%d %d 2\n", endX, startY);
        else if (endX == pX && endY == pY) printf("%d %d 4\n", startX, startY);
        else printf("%d %d 3\n", startX, endY);
        return;
    }    // 上面的代码可以不用写，但是为了防止递归栈过多，手动增大递归终止条件
    int midX = (startX + endX) / 2, midY = (startY + endY) / 2;    // 偏左 偏上
    if (pX <= midX && pY <= midY) {    // 左上区域
        printf("%d %d 1\n", midX + 1, midY + 1);    // 中央添加地毯
        solver(startX, midX, startY, midY, pX, pY);
        solver(startX, midX, midY + 1, endY, midX, midY + 1);
        solver(midX + 1, endX, startY, midY, midX + 1, midY);
        solver(midX + 1, endX, midY + 1, endY, midX + 1, midY + 1);
    }
    else if (pX <= midX && pY > midY) {    // 右上区域
        printf("%d %d 2\n", midX + 1, midY);
        solver(startX, midX, midY + 1, endY, pX, pY);
        solver(startX, midX, startY, midY, midX, midY);
        solver(midX + 1, endX, startY, midY, midX + 1, midY);
        solver(midX + 1, endX, midY + 1, endY, midX + 1, midY + 1);
    }
    else if (pX > midX && pY <= midY) {    // 左下区域
        printf("%d %d 3\n", midX, midY + 1);
        solver(midX + 1, endX, startY, midY, pX, pY);
        solver(startX, midX, startY, midY, midX, midY);
        solver(startX, midX, midY + 1, endY, midX, midY + 1);
        solver(midX + 1, endX, midY + 1, endY, midX + 1, midY + 1);
    }
    else {    // 右下区域
        printf("%d %d 4\n", midX, midY);
        solver(midX + 1, endX, midY + 1, endY, pX, pY);
        solver(startX, midX, startY, midY, midX, midY);
        solver(startX, midX, midY + 1, endY, midX, midY + 1);
        solver(midX + 1, endX, startY, midY, midX + 1, midY);
    }
}

int main() {
    int k, x, y; scanf("%d", &k);
    int startX = 1, startY = 1, endX = (1 << k), endY = (1 << k);
    scanf("%d%d", &x, &y);
    solver(startX, endX, startY, endY, x, y);
    return 0;
}

啥都没改一遍过 ~ （很简单嘛【doge】