P1228 地毯填补问题

这一题其实想通了并不难，如果现在还不知道怎么做的话可以去看这里：p1228 地毯填补问题。

但是这一题在具体写代码的时候涉及到很多的编码细节问题。直接上手写，会发现要写很多相似的代码，非常繁琐。这里介绍一种表驱动的方式帮助大家简化代码，代码已经加上了注释，欢迎交流讨论。

#include <cstdio>

int dx[4] = {0, 0, 1, 1};
int dy[4] = {0, 1, 0, 1}; 

// (x0, y0) 表示左上角方格，(x, y) 表示忽略的方格，k 表示方阵大小(2^k)
void solve(int x0, int y0, int x, int y, int k) {
    if (k == 1) {
        int _dx = x - x0;
        int _dy = y - y0;
        
        for (int i = 0; i < 4; i++) {
            if (dx[i] == _dx && dy[i] == _dy) {
                int __dx = (_dx + 1) & 1;  // % 2（位运算速度更快）
                int __dy = (_dy + 1) & 1;  // % 2
                printf("%d %d %d\n", x0 + __dx, y0 + __dy, i + 1);  // 取 (x, y) 的对角方格作为地毯中点
                return;
            }
        }
    }
    
    int p = (1 << (k - 1));
    int dx0[4] = {0, 0, p, p};
    int dy0[4] = {0, p, 0, p};
    int x1 = x0 + p - 1;
    int y1 = y0 + p - 1;

    bool flag = true;
    
    for (int i = 3; i >= 0; i--) {  // 从右下角开始迭代，确定 (x, y) 的位置
        int _x0 = x0 + dx0[i];  // (_x0, _y0) 表示四个左上角方格
        int _y0 = y0 + dy0[i];
        int _x1 = x1 + dx[i];   // (_x1, _y1) 表示最中间的四个方格
        int _y1 = y1 + dy[i];
        if (flag && x >= _x0 && y >= _y0) { // 确定 (x, y) 位置的判断条件（仔细体会）
            flag = false;
            solve(x1, y1, _x1, _y1, 1);     // 中间四个点也可以转化为一个子问题
            solve(_x0, _y0, x, y, k - 1);
        }
        else solve(_x0, _y0, _x1, _y1, k - 1);
    }
}

int main() {
    int k, x, y;
    scanf("%d%d%d", &k, &x, &y);
    solve(1, 1, x, y, k);
    return 0;
}