题目如下：
完美正方形
如果一些边长互不相同的正方形，可以恰好拼出一个更大的正方形，则称其为完美正方形。
历史上，人们花了很久才找到了若干完美正方形。比如：如下边长的22个正方形
2 3 4 6 7 8 12 13 14 15 16 17 18 21 22 23 24 26 27 28 50 60
如【图1.png】那样组合，就是一种解法。此时，
紧贴上边沿的是：60 50
紧贴下边沿的是：26 28 17 21 18
22阶完美正方形一共有8种。下面的组合是另一种：
2 5 9 11 16 17 19 21 22 24 26 30 31 33 35 36 41 46 47 50 52 61
如果告诉你该方案紧贴着上边沿的是从左到右依次为：47 46 61，
你能计算出紧贴着下边沿的是哪几个正方形吗？请提交紧贴着下边沿的正方形的边长，从左到右，用空格分开。
答案：50 33 30 41
![4PDCT}DV]X}DV)XWJI{F%E9](https://blog.kasora.moe/wp-content/uploads/2016/05/4PDCTDVXDVXWJIFE9.png)
去年比赛的时候这题死活出BUG查不出来，今年静下心尝试重写了一份，用时1.5h左右
大体思路是：
所有的方块的插入点一定是某两个方块的夹角点（或者正方形和边界的夹角），所以只要按层寻找方块的夹角即可。
这样寻找的好处就是，只需要判断正方形的第一层有无方块遮挡即可。
代码如下：
|
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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> using namespace std; //储存备用正方形 int sqlist[] = { 47, 46, 61, 2, 5, 9, 11, 16, 17, 19, 21, 22, 24, 26, 30, 31, 33, 35, 36, 41, 50, 52 }; //该号码正方形是否使用过 bool used[22]; //整个图像 int blocks[154][154]; //从坐标(x,y)开始将size*size的区域填充为num void fildblock(int x, int y, int size,int num) { for (int i = x; i < x + size; i++) for (int j = y; j < y + size; j++) blocks[i][j] = num; } //在坐标(x,y)处添加第sqid号正方形，nullnum为当前还有多少块方块未被填上 void addsq(int x, int y, int sqid,int nullnum) { //获取边长 int side = sqlist[sqid]; //判断填充是否合法 if (x + side > 154 || y + side > 154) return; for (int i = y; i < y + side; i++) if (blocks[x][i] != 0) return; //进行填充 fildblock(x, y, side, side); nullnum -= side*side; used[sqid] = true; //判断是否所有方块都被填满 if (nullnum == 0) { for (int i = 0; i < 153; i++) { if (blocks[153][i] != blocks[153][i + 1]) cout << blocks[153][i] << " "; } cout << blocks[153][153] << endl; return; } //寻找下一个方块的插入点 int tx = x; int ty = y; for (;;) { ty++; if (ty == 154) { ty = 0; tx++; } if (blocks[tx][ty] == 0) break; } //尝试插入方块 for (int i = 3; i < 22; i++) { if (!used[i]) { addsq(tx, ty, i, nullnum); } } //该方块插入失败，取消操作 fildblock(x, y, side, 0); used[sqid] = false; } int main() { //插入初始第一行的三个方块 for (int i = 0; i < 3; i++) used[i] = true; fildblock(0, 0, 47, 47); fildblock(0, 47, 46, 46); fildblock(0, 93, 61, 61); //尝试插入方块 for (int i = 3; i < 22; i++) { addsq(46, 47, i, 154*154-47*47-46*46-61*61); } return 0; } |