P1228 地毯填补问题

llqqhh · 2024-08-15 11:30:28 · 题解

P1228 地毯填补问题

看大家的题解都是从大往小分治，我来一篇从小到大的递归构

首先可以想到如果存在一个正方形， 我们就可以用一个同级别大小的L形地毯把它包裹成更大的正方形：

进一步地，我们可以用更大的L形地毯包住这个正方形：

用这种方法我们就可以从公主（边长为 1 的正方形）构造出任意 2^k 大小的正方形。

知道了这一点，我们的问题就变成了：如何构造出和任意和 2^k 大小的正方形匹配的L形地毯。一种构造方法如下图：

其中折线表示最基本的四种地毯之一，多边形表示基本地毯拼出的大地毯。

接着我们用这个大地毯构造更大的地毯：

其中多边形边框实际是不存在的，只是方便说明大小地毯之间的递归关系（应该没有人不知道吧）。

以下给出生成大地毯的代码：

void fillL(int x, int y, int siz, int dir) {
    if(siz == 0) {
        a[x][y] = dir;
        return;
    }
    if(dir == 1) {
        fillL(x, y, siz - 1, dir);
        fillL(x + (1 << siz - 1), y + (1 << siz - 1), siz - 1, dir);
        fillL(x + (1 << siz - 1), y - (1 << siz), siz - 1, 2);
        fillL(x - (1 << siz), y + (1 << siz - 1), siz - 1, 3);
    } else if(dir == 2) {
        fillL(x, y + (1 << siz - 1), siz - 1, dir);
        fillL(x + (1 << siz - 1), y, siz - 1, dir);
        fillL(x + (1 << siz - 1), y + (1 << siz + 1) - (1 << siz - 1), siz - 1, 1);
        fillL(x - (1 << siz), y, siz - 1, 4);
    } else if(dir == 3) {
        fillL(x, y + (1 << siz - 1), siz - 1, dir);
        fillL(x + (1 << siz - 1), y, siz - 1, dir);
        fillL(x + (1 << siz + 1) - (1 << siz - 1), y + (1 << siz - 1), siz - 1, 1);
        fillL(x, y - (1 << siz), siz - 1, 4);
    } else {
        fillL(x, y, siz - 1, dir);
        fillL(x + (1 << siz - 1), y + (1 << siz - 1), siz - 1, dir);
        fillL(x + (1 << siz + 1) - (1 << siz - 1), y, siz - 1, 2);
        fillL(x, y + (1 << siz + 1) - (1 << siz - 1), siz - 1, 3);
    }
}

代码中 siz 表示当前要处理的地毯大小，siz = 0 表示当前处理到最基本的地毯， siz = 1 表示当前需要处理经过一层递归的地毯，以此类推；dir 表示当前要处理的地毯的方向； x, y 表示当前要处理 的 地毯 的 拐点 的 左上角 的 坐标。说的有点抽象，上图！

在以上四种情况中 x, y 表示图中红色点的位置。

除了填充地毯，我们还需要一个为正方形匹配地毯的函数，为什么呢？

对于中间的红点，有旁边的四种地毯可以匹配。但是我们真正需要的只有右上角这个橙色的地毯。因为你从四个地毯中选择了一个和红点匹配后的下一轮匹配必须能找到一个更大的地毯可以和这个正方形匹配并且能够在整张地图中放得下。即你只有在选择橙色地毯后才能继续和棕色地毯匹配，否则你在下一轮就找不到地毯能和这一状态匹配。上代码：

void fillb(int x, int y, int dep) {
    if(dep == k) return;
    int bx = x % (1 << dep + 1) / (1 << dep);
    int by = y % (1 << dep + 1) / (1 << dep);
    if(bx == 0 && by == 0) {
        fillL(x + (1 << dep), y + (1 << dep), dep, 1);
        fillb(x, y, dep + 1);
    } else if(bx == 0 && by == 1) {
        fillL(x + (1 << dep), y - (1 << dep), dep, 2);
        fillb(x, y - (1 << dep), dep + 1);
    } else if(bx == 1 && by == 0) {
        fillL(x - (1 << dep), y + (1 << dep), dep, 3);
        fillb(x - (1 << dep), y, dep + 1);
    } else {
        fillL(x - (1 << dep), y - (1 << dep), dep, 4);
        fillb(x - (1 << dep), y - (1 << dep), dep + 1);
    }
}

代码中 bx, by 是为了方便讨论接下来要和什么方向的地毯匹配。同时为了方便处理出 bx, by 我们需要把地图下表从 0 开始排。

以下给出完整代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1024;
int k, cx, cy;
int a[N][N];

void fillL(int x, int y, int siz, int dir) {
    if(siz == 0) {
        a[x][y] = dir;
        return;
    }
    if(dir == 1) {
        fillL(x, y, siz - 1, dir);
        fillL(x + (1 << siz - 1), y + (1 << siz - 1), siz - 1, dir);
        fillL(x + (1 << siz - 1), y - (1 << siz), siz - 1, 2);
        fillL(x - (1 << siz), y + (1 << siz - 1), siz - 1, 3);
    } else if(dir == 2) {
        fillL(x, y + (1 << siz - 1), siz - 1, dir);
        fillL(x + (1 << siz - 1), y, siz - 1, dir);
        fillL(x + (1 << siz - 1), y + (1 << siz + 1) - (1 << siz - 1), siz - 1, 1);
        fillL(x - (1 << siz), y, siz - 1, 4);
    } else if(dir == 3) {
        fillL(x, y + (1 << siz - 1), siz - 1, dir);
        fillL(x + (1 << siz - 1), y, siz - 1, dir);
        fillL(x + (1 << siz + 1) - (1 << siz - 1), y + (1 << siz - 1), siz - 1, 1);
        fillL(x, y - (1 << siz), siz - 1, 4);
    } else {
        fillL(x, y, siz - 1, dir);
        fillL(x + (1 << siz - 1), y + (1 << siz - 1), siz - 1, dir);
        fillL(x + (1 << siz + 1) - (1 << siz - 1), y, siz - 1, 2);
        fillL(x, y + (1 << siz + 1) - (1 << siz - 1), siz - 1, 3);
    }
}

void fillb(int x, int y, int dep) {
    if(dep == k) return;
    int bx = x % (1 << dep + 1) / (1 << dep);
    int by = y % (1 << dep + 1) / (1 << dep);
    if(bx == 0 && by == 0) {
        fillL(x + (1 << dep), y + (1 << dep), dep, 1);
        fillb(x, y, dep + 1);
    } else if(bx == 0 && by == 1) {
        fillL(x + (1 << dep), y - (1 << dep), dep, 2);
        fillb(x, y - (1 << dep), dep + 1);
    } else if(bx == 1 && by == 0) {
        fillL(x - (1 << dep), y + (1 << dep), dep, 3);
        fillb(x - (1 << dep), y, dep + 1);
    } else {
        fillL(x - (1 << dep), y - (1 << dep), dep, 4);
        fillb(x - (1 << dep), y - (1 << dep), dep + 1);
    }
}

int main() {
    cin >> k >> cx >> cy;
    cx --, cy --;
    fillb(cx, cy, 0);
    for(int i = 0; i < 1 << k; i ++) {
        for(int j = 0; j < 1 << k; j ++)
            if(a[i][j]) cout << i + 1 << ' ' << j + 1 << ' ' << a[i][j] << '\n';
    }
}

画图不易，点个赞再走吧QAQ