【转】第六届蓝桥杯决赛 第二题 完美正方形 （线段树）

请提交紧贴着下边沿的正方形的边长，从左到右，用空格分开。

答案：50 33 30 41

#include <iostream>
#include <String.h>
using namespace std;
int a[]={2, 5 ,9 ,11 ,16, 17, 19, 21, 22, 24, 26, 30, 31, 33, 35, 36, 41, 50 ,52  };	//正方形 
int vis[19];	//访问数组	
int que[30];	// 存储最下行每个正方形大小 
int fon=0;		//最下行正方形索引 
int map[154][154];		//填充为1 未填充为0 

void make(int x,int y,int k,int u)		//填充和清除正方形 	u为1为填充 否则为清空 
{
	if(u==1)
	for(int i=x;i<x+k;i++)
		for(int j=y;j<y+k;j++)
		{
			map[i][j]=1;
		}
	else
	for(int i=x;i<x+k;i++)
		for(int j=y;j<y+k;j++)
		{
			map[i][j]=0;
		}
}

int panduan(int x,int y,int k)		// 当前点 x y 填充大小k 
{
	if(x+k>154)return 0;
	if(y+k>154)return 0;
	//判断将被填入的正方形部分是否有已经被填充部分 
	for(int i=x;i<x+k;i++)
		for(int j=y;j<y+k;j++)
		{
			if(map[i][j]==1)return 0;	
		}
		return 1;
}
int f(int k)	//k为遍历数组的索引 
{
	if(k>=19)		//完成遍历 
	{
		for(int i=0;i<fon;i++)
			cout<<que[i]<<" ";
			cout<<endl;
		return 1;
	}
	for(int j=0;j<154;j++)
	for(int i=0;i<154;i++)
		{
			if(map[i][j]==0)	//如果未填充 
			{
				for(int z=0;z<19;z++)		//搜索数组中的正方形 
				{
					if(vis[z]==0 && panduan(i,j,a[z]))	//如果正方形未使用并且符合填充要求 
					{
						int flog=0;
						if(i+a[z]==154)
						{
							 que[fon++]=a[z];
							 flog=1;
						 }
						vis[z]=1;
						make(i,j,a[z],1);
						if(f(k+1)) return 1;		//如果满足要求填充下一块 
						if(flog) 		//如果填过一块，从前一块开始填 
							fon--; 
						vis[z]=0;
						make(i,j,a[z],0);
					}
				}
				return 0;
			}
		}
		return 0;
}
int main()
{	
	make(0,0,47,1);make(0,47,46,1);make(0,93,61,1);
	f(0);

	return 0;
}