题目如下:
完美正方形
如果一些边长互不相同的正方形,可以恰好拼出一个更大的正方形,则称其为完美正方形。
历史上,人们花了很久才找到了若干完美正方形。比如:如下边长的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
去年比赛的时候这题死活出BUG查不出来,今年静下心尝试重写了一份,用时1.5h左右
大体思路是:
所有的方块的插入点一定是某两个方块的夹角点(或者正方形和边界的夹角),所以只要按层寻找方块的夹角即可。
这样寻找的好处就是,只需要判断正方形的第一层有无方块遮挡即可。
代码如下:
#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; }