洛谷 P1228 地毯填补问题

// P1228 —— 「毯子形状 1/2/3/4」到底怎么编号？拿样例把它反推出来
//
// 输入：无（原站那组样例写死在里面）
// 输出：24 种猜法逐个验一遍，最后剩下的那一种就是答案
//
// ★ 这份程序解决的是这道题**唯一真正的门槛**：
//   题面说毯子「只能有四种选择（如图）」—— 而那张图我们抄不过来（题面转录只有文字）。
//   编号猜错的话，算法一个字都没错，交上去照样全错。
//
// ★★ 但编号不用猜：**原站给了一组样例，样例本身就把编号锁死了。**
//   一块毯子占 2x2 里的三格，(x,y) 是拐角，另外两格必然是「上或下」＋「左或右」。
//   于是 c=1..4 到底对应哪四种，一共只有 4! = 24 种可能 ——
//   把样例那 21 块按每种猜法摆到 8x8 的棋盘上，**能恰好铺满（公主那格除外）的只有一种**。

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

// 原站样例：k = 3（8x8），公主在 (3,3)，21 块毯子
const int SK = 3, SX = 3, SY = 3;
const int SAMPLE[21][3] = {
    {5,5,1},{2,2,4},{1,1,4},{1,4,3},{4,1,2},{4,4,1},{2,7,3},
    {1,5,4},{1,8,3},{3,6,3},{4,8,1},{7,2,2},{5,1,4},{6,3,2},
    {8,1,2},{8,4,1},{7,7,1},{6,6,1},{5,8,3},{8,5,2},{8,8,1},
};

// 四种「另外两格往哪儿伸」：(dx, dy) —— dx = -1 上 / +1 下，dy = -1 左 / +1 右
const int DX[4] = {-1, -1, +1, +1};
const int DY[4] = {-1, +1, -1, +1};
const char* NAME[4] = {"上 + 左（缺口在左上）", "上 + 右（缺口在右上）",
                       "下 + 左（缺口在左下）", "下 + 右（缺口在右下）"};

int main() {
    int n = 1 << SK;
    int order[4] = {0, 1, 2, 3};
    int okCount = 0, okOrder[4] = {0, 0, 0, 0};
    int tried = 0;

    do {
        tried++;
        vector<vector<int>> g(n + 2, vector<int>(n + 2, 0));
        bool ok = true;
        string why;
        for (auto& p : SAMPLE) {
            int x = p[0], y = p[1], c = p[2];
            int d = order[c - 1];                       // 这一种猜法里，c 对应哪个方向
            int cell[3][2] = {{x, y}, {x + DX[d], y}, {x, y + DY[d]}};
            for (auto& q : cell) {
                int a = q[0], b = q[1];
                if (a < 1 || a > n || b < 1 || b > n) { ok = false; why = "有格子出界"; break; }
                if (a == SX && b == SY) { ok = false; why = "盖住了公主"; break; }
                if (g[a][b]) { ok = false; why = "两块毯子重叠"; break; }
                g[a][b] = 1;
            }
            if (!ok) break;
        }
        int covered = 0;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) covered += g[i][j];
        if (ok && covered != n * n - 1) { ok = false; why = "有格子没盖到"; }

        printf("猜法 %2d：c=1->%d c=2->%d c=3->%d c=4->%d   %s\n", tried,
               order[0] + 1, order[1] + 1, order[2] + 1, order[3] + 1,
               ok ? "★ 铺满了" : ("x " + why).c_str());
        if (ok) { okCount++; for (int i = 0; i < 4; i++) okOrder[i] = order[i]; }
    } while (next_permutation(order, order + 4));

    printf("\n24 种猜法里，能把样例铺满的有 %d 种。\n", okCount);
    if (okCount == 1) {
        printf("⇒ 编号是唯一确定的，不用猜：\n\n");
        for (int c = 1; c <= 4; c++) {
            int d = okOrder[c - 1];
            printf("   c = %d  ->  另外两格是 (x%+d,y) 和 (x,y%+d)  ->  %s\n",
                   c, DX[d], DY[d], NAME[d]);
        }
    }
    return 0;
}

// P1228 自检：把一份答案还原成棋盘，看它到底合不合法
//
// 输入：第一行 k；第二行 x y（公主）；接下来若干行 "x y c"，读到文件尾
// 输出：一行结论。合法就报「n x n 的 N 格恰好各盖一次」，不合法就报是哪一种错
//       （四种错和原站 spj 的报错代码一一对应：c 越界 / 坐标越界 / 重复覆盖 / 有格子没盖到）
//
// ★ 这份程序的意义：**这道题不用交到洛谷就能自己判对错。**
//   它是 special judge 题（方案不唯一），所以「和样例逐字节相同」这条尺子在这儿是错的 ——
//   换一份合法答案照样能过。能判的只有「覆盖关系对不对」。

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

const int DX[5] = {0, -1, -1, +1, +1};   // c = 1..4：另外两格往哪儿伸
const int DY[5] = {0, -1, +1, -1, +1};

int main() {
    int k, px, py;
    if (scanf("%d %d %d", &k, &px, &py) != 3) { printf("读不到 k 和公主坐标\n"); return 0; }
    int n = 1 << k;
    vector<vector<int>> g(n + 2, vector<int>(n + 2, 0));

    int x, y, c, pieces = 0;
    while (scanf("%d %d %d", &x, &y, &c) == 3) {
        pieces++;
        if (c < 1 || c > 4) { printf("第 %d 块：c = %d 越界（spj 错误 1）\n", pieces, c); return 0; }
        int cell[3][2] = {{x, y}, {x + DX[c], y}, {x, y + DY[c]}};
        for (auto& q : cell) {
            int a = q[0], b = q[1];
            if (a < 1 || a > n || b < 1 || b > n) {
                printf("第 %d 块：格子 (%d,%d) 越界（spj 错误 2）\n", pieces, a, b); return 0;
            }
            if (a == px && b == py) {
                printf("第 %d 块：盖住了公主 (%d,%d)（spj 错误 3）\n", pieces, px, py); return 0;
            }
            if (g[a][b]) {
                printf("第 %d 块：格子 (%d,%d) 被盖了两次（spj 错误 3）\n", pieces, a, b); return 0;
            }
            g[a][b] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!g[i][j] && !(i == px && j == py)) {
                printf("格子 (%d,%d) 从没被盖过（spj 错误 4）\n", i, j); return 0;
            }
    printf("合法：%d x %d 的 %d 格恰好各盖一次，公主 (%d,%d) 没被盖，一共 %d 块毯子\n",
           n, n, n * n - 1, px, py, pieces);
    return 0;
}

// 洛谷 P1228 —— 第 ① 版：分治一个字都没错，**编号是猜的**（所以全错）
//
// 输入：第一行 k（迷宫是 2^k x 2^k，0 < k <= 10）；第二行 x y（公主所在的行、列）
// 输出：每行 "x y c" —— 一块毯子的拐角坐标，和它的形状编号
//
// 分治的形状（和 P5461 同源）：
//   把正方形切成四块，公主在其中一块里；
//   在**正中心**放一块毯子，盖住另外三块各自靠中心的那一格 ——
//   于是那三块也「各有一个已经被占住的格子」，和公主那一块变成了同一个问题。
//   ⇒ 四块各自递归，边长 1 时停。
//
// ★ 编号 c 不是猜的，是 p1228Derive.cpp 拿原站样例反推出来的（24 选 1，唯一）：
//     c = 1 缺口在左上   c = 2 缺口在右上   c = 3 缺口在左下   c = 4 缺口在右下
//   而「缺口」正好就是公主/已占格所在的那个象限 ⇒ **c 就是象限编号**，一行都不用记。
//
// ⚠ 输出量：k = 10 时是 (1024*1024 - 1) / 3 = 349525 行 ——
//   和 P5461 一样，这道题「打得快」和「算得快」都要管，所以关了同步、不用 endl。

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

/**
 * 铺满左上角为 (r,c)、边长 len 的正方形，其中 (hr,hc) 这一格已经被占住（公主或上一块毯子）。
 */
void solve(int r, int c, int len, int hr, int hc) {
    if (len == 1) return;
    int h = len / 2;
    int mr = r + h - 1, mc = c + h - 1;        // 中心那 2x2 的左上格

    bool top = (hr <= mr), left = (hc <= mc);  // 已占格落在哪个象限
    // ⚠ 这一版把编号猜成了「顺时针」：1 左上、2 右上、3 右下、4 左下。
    //   看着比「先上下、再左右」更自然 —— 而它把 3 和 4 换了个个儿。
    int quad = top ? (left ? 1 : 2) : (left ? 4 : 3);

    // 毯子的拐角 = 中心 2x2 里、和「已占格那个象限」对角的那一格
    int cx = top ? mr + 1 : mr;
    int cy = left ? mc + 1 : mc;
    printf("%d %d %d\n", cx, cy, quad);

    // 四个象限各自递归：已占格那一块用 (hr,hc)，另外三块用刚被这块毯子盖住的那一格
    solve(r,      c,      h, top && left  ? hr : mr,     top && left  ? hc : mc);
    solve(r,      c + h,  h, top && !left ? hr : mr,     top && !left ? hc : mc + 1);
    solve(r + h,  c,      h, !top && left ? hr : mr + 1, !top && left ? hc : mc);
    solve(r + h,  c + h,  h, !top && !left? hr : mr + 1, !top && !left? hc : mc + 1);
}

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

// 洛谷 P1228 地毯填补问题 —— 正解：分治，每次在中心放一块毯子
//
// 输入：第一行 k（迷宫是 2^k x 2^k，0 < k <= 10）；第二行 x y（公主所在的行、列）
// 输出：每行 "x y c" —— 一块毯子的拐角坐标，和它的形状编号
//
// 分治的形状（和 P5461 同源）：
//   把正方形切成四块，公主在其中一块里；
//   在**正中心**放一块毯子，盖住另外三块各自靠中心的那一格 ——
//   于是那三块也「各有一个已经被占住的格子」，和公主那一块变成了同一个问题。
//   ⇒ 四块各自递归，边长 1 时停。
//
// ★ 编号 c 不是猜的，是 p1228Derive.cpp 拿原站样例反推出来的（24 选 1，唯一）：
//     c = 1 缺口在左上   c = 2 缺口在右上   c = 3 缺口在左下   c = 4 缺口在右下
//   而「缺口」正好就是公主/已占格所在的那个象限 ⇒ **c 就是象限编号**，一行都不用记。
//
// ⚠ 输出量：k = 10 时是 (1024*1024 - 1) / 3 = 349525 行 ——
//   和 P5461 一样，这道题「打得快」和「算得快」都要管，所以关了同步、不用 endl。

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

/**
 * 铺满左上角为 (r,c)、边长 len 的正方形，其中 (hr,hc) 这一格已经被占住（公主或上一块毯子）。
 */
void solve(int r, int c, int len, int hr, int hc) {
    if (len == 1) return;
    int h = len / 2;
    int mr = r + h - 1, mc = c + h - 1;        // 中心那 2x2 的左上格

    bool top = (hr <= mr), left = (hc <= mc);  // 已占格落在哪个象限
    int quad = (top ? 0 : 2) + (left ? 0 : 1) + 1;   // 1 左上 2 右上 3 左下 4 右下

    // 毯子的拐角 = 中心 2x2 里、和「已占格那个象限」对角的那一格
    int cx = top ? mr + 1 : mr;
    int cy = left ? mc + 1 : mc;
    printf("%d %d %d\n", cx, cy, quad);

    // 四个象限各自递归：已占格那一块用 (hr,hc)，另外三块用刚被这块毯子盖住的那一格
    solve(r,      c,      h, top && left  ? hr : mr,     top && left  ? hc : mc);
    solve(r,      c + h,  h, top && !left ? hr : mr,     top && !left ? hc : mc + 1);
    solve(r + h,  c,      h, !top && left ? hr : mr + 1, !top && left ? hc : mc);
    solve(r + h,  c + h,  h, !top && !left? hr : mr + 1, !top && !left? hc : mc + 1);
}

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