2015蓝桥杯 C/C++B组 完美正方形

题目如下：

完美正方形

如果一些边长互不相同的正方形，可以恰好拼出一个更大的正方形，则称其为完美正方形。
历史上，人们花了很久才找到了若干完美正方形。比如：如下边长的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;
}