P1228. 地毯填补问题

发表于 分类于 阅读次数： Waline： 本文字数： 595 阅读时长 ≈ 2 分钟

考点

  • 分治

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;

int board[1025][1025];

void f(int x_bg, int x_ed, int y_bg, int y_ed, int princess_x, int princess_y)
{
    int x_mid = (x_bg + x_ed) / 2, y_mid = (y_bg + y_ed) / 2;
    if (princess_x <= x_mid && princess_y <= y_mid)
    { // 公主在左上方
        printf("%d %d %d\n", x_mid + 1, y_mid + 1, 1);
        if (x_bg == x_mid && y_bg == y_mid)
            return;
        //左上，右上，左下，右下四个方向更新各自的公主位置后，继续递归
        f(x_bg, x_mid, y_bg, y_mid, princess_x, princess_y);
        f(x_bg, x_mid, y_mid + 1, y_ed, x_mid, y_mid + 1);
        f(x_mid + 1, x_ed, y_bg, y_mid, x_mid + 1, y_mid);
        f(x_mid + 1, x_ed, y_mid + 1, y_ed, x_mid + 1, y_mid + 1);
    }
    else if (princess_x <= x_mid && princess_y > y_mid)
    {
        // 公主在右上方
        printf("%d %d %d\n", x_mid + 1, y_mid, 2);
        if (x_bg == x_mid && y_bg == y_mid)
            return;
        f(x_bg, x_mid, y_bg, y_mid, x_mid, y_mid);
        f(x_bg, x_mid, y_mid + 1, y_ed, princess_x, princess_y);
        f(x_mid + 1, x_ed, y_bg, y_mid, x_mid + 1, y_mid);
        f(x_mid + 1, x_ed, y_mid + 1, y_ed, x_mid + 1, y_mid + 1);
    }
    else if (princess_x > x_mid && princess_y <= y_mid)
    {
        // 公主在左下方
        printf("%d %d %d\n", x_mid, y_mid + 1, 3);
        if (x_bg == x_mid && y_bg == y_mid)
            return;
        f(x_bg, x_mid, y_bg, y_mid, x_mid, y_mid);
        f(x_bg, x_mid, y_mid + 1, y_ed, x_mid, y_mid + 1);
        f(x_mid + 1, x_ed, y_bg, y_mid, princess_x, princess_y);
        f(x_mid + 1, x_ed, y_mid + 1, y_ed, x_mid + 1, y_mid + 1);
    }
    else
    {
        // 公主在右下方
        printf("%d %d %d\n", x_mid, y_mid, 4);
        if (x_bg == x_mid && y_bg == y_mid)
            return;
        f(x_bg, x_mid, y_bg, y_mid, x_mid, y_mid);
        f(x_bg, x_mid, y_mid + 1, y_ed, x_mid, y_mid + 1);
        f(x_mid + 1, x_ed, y_bg, y_mid, x_mid + 1, y_mid);
        f(x_mid + 1, x_ed, y_mid + 1, y_ed, princess_x, princess_y);
    }
}

int main()
{
    int n, princess_x, princess_y;
    cin >> n >> princess_x >> princess_y;
    f(1, pow(2, n), 1, pow(2, n), princess_x, princess_y);
    return 0;
}

思路

经典的分治题

公主必出现在当前大正方形的左上，右上，左下，右下四个方位；那么大正方形中心填充的地毯缺口就会正对公主那个方位

因此，每一次都只需要填充当前大正方形的中心，然后分别向四个方位的四个小正方形递归

假设当前公主出现在左上方，那么填充中心的应当是1，随后向四个方位递归：

  • 公主坐标不变，向左上方递归，边界收缩；
  • 公主坐标改为大正方形中心填充地毯的右上角部分，向右上方递归，边界收缩；
  • 公主坐标改为大正方形中心填充地毯的左下角部分，向左下方递归，边界收缩；
  • 公主坐标改为大正方形中心填充地毯的右下角部分，向右下方递归，边界收缩；

循环往复，直到当前大正方形是2 * 2的规格，无法再分