洛谷P1228 地毯填补问题（好题，难题）

nijigasaki14 / 2023-09-01 / 原文

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int k, x, y;
 4 
 5 int judge(int x, int y, int gx, int gy, int len) // 判断障碍物在哪个区块
 6 {
 7     if (gx <= x + len / 2 - 1 && gy <= y + len / 2 - 1)
 8         return 1;
 9     else if (gx <= x + len / 2 - 1 && gy >= y + len / 2)
10         return 2;
11     else if (gx >= x + len / 2 && gy <= y + len / 2 - 1)
12         return 3;
13     else
14         return 4;
15 }
16 
17 void f(int x, int y, int gx, int gy, int len) // gx,gy为障碍物的坐标, len为迷宫的长度
18 {
19     if (len == 1)
20         return;
21     if (judge(x, y, gx, gy, len) == 1)
22     {
23         cout << x + len / 2 << " " << y + len / 2 << " " << 1 << endl;
24         f(x, y, gx, gy, len >> 1);
25         f(x, y + len / 2, x + len / 2 - 1, y + len / 2, len >> 1);
26         f(x + len / 2, y, x + len / 2, y + len / 2 - 1, len >> 1);
27         f(x + len / 2, y + len / 2, x + len / 2, y + len / 2, len >> 1);
28     }
29     else if (judge(x, y, gx, gy, len) == 2)
30     {
31         cout << x + len / 2 << " " << y + len / 2 - 1 << " " << 2 << endl;
32         f(x, y, x + len / 2 - 1, y + len / 2 - 1, len >> 1);
33         f(x, y + len / 2, gx, gy, len >> 1);
34         f(x + len / 2, y, x + len / 2, y + len / 2 - 1, len >> 1);
35         f(x + len / 2, y + len / 2, x + len / 2, y + len / 2, len >> 1);
36     }
37     else if (judge(x, y, gx, gy, len) == 3)
38     {
39         cout << x + len / 2 - 1 << " " << y + len / 2 << " " << 3 << endl;
40         f(x, y, x + len / 2 - 1, y + len / 2 - 1, len >> 1);
41         f(x, y + len / 2, x + len / 2 - 1, y + len / 2, len >> 1);
42         f(x + len / 2, y, gx, gy, len >> 1);
43         f(x + len / 2, y + len / 2, x + len / 2, y + len / 2, len >> 1);
44     }
45     else if (judge(x, y, gx, gy, len) == 4)
46     {
47         cout << x + len / 2 - 1 << " " << y + len / 2 - 1 << " " << 4 << endl;
48         f(x, y, x + len / 2 - 1, y + len / 2 - 1, len >> 1);
49         f(x, y + len / 2, x + len / 2 - 1, y + len / 2, len >> 1);
50         f(x + len / 2, y, x + len / 2, y + len / 2 - 1, len >> 1);
51         f(x + len / 2, y + len / 2, gx, gy, len >> 1);
52     }
53 }
54 
55 int main()
56 {
57     cin >> k >> x >> y;
58     f(1, 1, x, y, 1 << k);
59 }