poj 1020 Anniversary Cake dfs的灵活结构

题意:

给一个目标正方形边长和n个小正方形的边长,,问是否可以用这n个小正方形填满目标正方形。

分析:

dfs不一开始就定好放入顺序,而是用已放入的个数代表深搜维度。

代码:

#include <iostream>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;}

背着背包的路上,看过许多人,

poj 1020 Anniversary Cake dfs的灵活结构

相关文章:

你感兴趣的文章:

标签云: