程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 1020 Anniversary Cake dfs的靈活結構

poj 1020 Anniversary Cake dfs的靈活結構

編輯:關於C++

題意:

給一個目標正方形邊長和n個小正方形的邊長,問是否可以用這n個小正方形填滿目標正方形。

分析:

dfs不一開始就定好放入順序,而是用已放入的個數代表深搜維度。

代碼:

 

#include 
using namespace std;

int box_size;
int n;
int size_num[16];
int col[64];

bool dfs(int cnt)
{
	if(cnt==n)
		return true;
	int minx=INT_MAX,col_index;
	for(int i=1;i<=box_size;++i)
		if(minx>col[i]){
			minx=col[i];
			col_index=i;
		}
	for(int size=10;size>=1;--size){
		if(!size_num[size]) continue;
		if(box_size-col[col_index]>=size&&box_size-col_index+1>=size){
			int t=0;
			for(int c=col_index;c<=col_index+size-1;++c){
				if(col[c]==col[col_index]){
					++t;
					continue;
				}
				break;
			}
			if(t==size){
				size_num[size]--;
				for(int c=col_index;c<=col_index+size-1;++c)
					col[c]+=size;
				if(dfs(cnt+1)) return true;
				size_num[size]++;
				for(int c=col_index;c<=col_index+size-1;++c)
					col[c]-=size;
			}
		}
	}
	return false;		   	
}

int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--){
		memset(size_num,0,sizeof(size_num));
		memset(col,0,sizeof(col));
		scanf("%d%d",&box_size,&n);		
		int cnt=0,area=0;
		for(int i=1;i<=n;++i){
			int size;
			scanf("%d",&size);
			++size_num[size];
			area+=size*size;
			if(size>box_size/2) ++cnt;
		}
		if(cnt>1||area!=box_size*box_size){
			puts("HUTUTU!");
			continue;
		}	
		if(dfs(0)) puts("KHOOOOB!");
		else puts("HUTUTU!");
	}
	return 0;	
} 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved