pta铺地砖c++

7-1 铺地砖

分数 100

全屏浏览题目

切换布局

作者 李强

单位 滨州学院

这个思路没有使用边长size，二分，而是以坐标为主。

有一个游泳池底，划分成了2n×2n（其中n是不超过10的正整数）的网格，每一小格都是正方形，其中有一小格是排水口。

下图展示了当n=4时，在坐标(11,11)上有一个排水口的情景。

现允许用4种形状（大小为2×2但是缺1×1的一角，如果考虑旋转和反转，实质上是同一种）的地砖进行铺设，要求排水口不能被覆盖，其他小格恰被一块地砖覆盖。

请输出铺设方案。

输入格式:

一行由空格隔开的3个数字n,x,y，其中n如上述题面所示，x,y表示排水孔所在的坐标。1≤n≤10,1≤x≤2n,1≤y≤2n

输出格式:

多行输出。

每块地砖占一行，由7个整数tx1​y1​x2​y2​x3​y3​构成，其中t是地砖的类型编号(1∼4)，xi​yi​是各类型地砖对应位置覆盖的小格坐标。

所有数字由1个空格隔开，行首行尾不要有多余的空格。

输出任意一种合法的顺序即可。

例如，对于上述24×24的网格最右上角如果用类型2的地砖进行铺设，覆盖其中3个小格子，则输出2 1 16 1 15 2 16。表示类型2的地砖，①覆盖最右上角的坐标为(1, 16)的小格，自然地，②、③ 分别覆盖(1, 15)和(2, 16)。

输入样例:

1 2 2

输出样例:

1 1 1 1 2 2 1

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

代码如下

#include <iostream>
using namespace std;
// 创建二维数组
int array[1025][1025] = {0};int recursion(int x1, int y1, int x4, int y4, int kx, int ky)
{// 如果是最小的小块1*1的就结束// 通过坐标确定if (y1 == y4 && x1 == x4)return 0;// 不是最小的，划分为四部分，并标记没有排水口的三部分离中心点最近的小格int c = (x4 + x1) / 2, d = (y4 + y1) / 2; // 取中心左上坐标// 1.标记点在左上if (kx <= c && ky <= d) // 通过坐标确定排水口的位置{// 判断类型写入其类型数字// 根据排水口位置确定离中心近的三个小格的类型array[c][d + 1] = 3, array[c + 1][d] = 3, array[c + 1][d + 1] = 3;// 划分成四个块并传入该块标记点recursion(x1, y1, c, d, kx, ky);recursion(x1, d + 1, c, y4, c, d + 1);recursion(c + 1, y1, x4, d, c + 1, d);recursion(c + 1, d + 1, x4, y4, c + 1, d + 1);}// 2.标记点在右上else if (kx <= c && ky > d){array[c][d] = 4, array[c + 1][d] = 4, array[c + 1][d + 1] = 4;recursion(x1, y1, c, d, c, d);recursion(x1, d + 1, c, y4, kx, ky);recursion(c + 1, y1, x4, d, c + 1, d);recursion(c + 1, d + 1, x4, y4, c + 1, d + 1);}// 3.出水口在左下else if (kx > c && ky <= d){array[c][d] = 2, array[c][d + 1] = 2, array[c + 1][d + 1] = 2;recursion(x1, y1, c, d, c, d);recursion(x1, d + 1, c, y4, c, d + 1);recursion(c + 1, y1, x4, d, kx, ky);recursion(c + 1, d + 1, x4, y4, c + 1, d + 1);}// 4.出水口在右下else if (kx > c && ky > d){array[c][d] = 1, array[c][d + 1] = 1, array[c + 1][d] = 1;recursion(x1, y1, c, d, c, d);recursion(x1, d + 1, c, y4, c, d + 1);recursion(c + 1, y1, x4, d, c + 1, d);recursion(c + 1, d + 1, x4, y4, kx, ky);}return 0;// 划分成四块
}int output(int i, int j)
{if (array[i][j] == 1){// 按此类型顺序输出即可// i，j是此类型最左边里的最上边的printf("1 %d %d %d %d %d %d\n", i, j, i, j + 1, i + 1, j);// 输出完此类型归零，防止2次输出array[i][j] = 0, array[i][j + 1] = 0, array[i + 1][j] = 0;}if (array[i][j] == 2){printf("2 %d %d %d %d %d %d\n", i, j + 1, i, j, i + 1, j + 1), array[i][j + 1] = 0, array[i][j] = 0, array[i + 1][j + 1] = 0;}if (array[i][j] == 3){printf("3 %d %d %d %d %d %d\n", i + 1, j, i + 1, j - 1, i, j), array[i][j] = 0, array[i + 1][j - 1] = 0, array[i + 1][j] = 0;}if (array[i][j] == 4){printf("4 %d %d %d %d %d %d\n", i + 1, j, i + 1, j + 1, i, j), array[i][j] = 0, array[i + 1][j + 1] = 0, array[i + 1][j] = 0;}return 0;
}int main()
{int n, kx, ky;int x4 = 1, y4 = 1;cin >> n >> kx >> ky;for (int i = 0; i < n; i++)x4 *= 2;y4 = x4;            // 初始化地图右下角坐标array[kx][ky] = -1; // 进行标记// 递归调用recursion(1, 1, x4, y4, kx, ky); // 左上坐标(x1,y1)，右下坐标(x4,y4)，标记点坐标(x,y)// 输出for (int i = 1; i <= x4; i++){for (int j = 1; j <= y4; j++){// 从第一行有序输出，最先输出到的一定是此类型最左边的// 如果最左边有两个就是其中最上边的if (array[i][j] != 0)output(i, j);}}return 0;
}