首页 > 代码库 > poj 2585 Window Pains 暴力枚举排列
poj 2585 Window Pains 暴力枚举排列
题意:
在4*4的格子中有9个窗体,窗体会覆盖它之下的窗体,问是否存在一个窗体放置的顺序使得最后的结果与输入同样。
分析:
在数据规模较小且不须要剪枝的情况下能够暴力(思路清晰代码简单),暴力一般分为枚举子集(for(s=0;s<1<<n;++s))和枚举排列(next_permutation)。
代码:
//poj 2585 //sep9 #include <iostream> #include <algorithm> using namespace std; int order[10]; int a[8][8],tmp[8][8]; char s[16]; int main() { while(1){ scanf("%s",s); if(s[0]=='E') break; int i,j; for(i=0;i<4;++i) for(j=0;j<4;++j) scanf("%d",&a[i][j]); int ok=0; for(i=1;i<=9;++i) order[i]=i; do{ for(i=0;i<4;++i) for(j=0;j<4;++j) tmp[i][j]=0; for(i=1;i<=9;++i){ int t=order[i]; tmp[(t-1)/3][(t-1)%3]=t; tmp[(t-1)/3][(t-1)%3+1]=t; tmp[(t-1)/3+1][(t-1)%3]=t; tmp[(t-1)/3+1][(t-1)%3+1]=t; } int equal=1; for(i=0;i<4&&equal;++i) for(j=0;j<4&&equal;++j) if(a[i][j]!=tmp[i][j]) equal=0; if(equal==1){ ok=1; break; } }while(next_permutation(order+1,order+10)); if(ok==0) puts("THESE WINDOWS ARE BROKEN"); else puts("THESE WINDOWS ARE CLEAN"); scanf("%*s"); } return 0; }
poj 2585 Window Pains 暴力枚举排列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。