当前位置: 代码迷 >> 综合 >> poj 2585 Window Pains 暴力枚举排列
  详细解决方案

poj 2585 Window Pains 暴力枚举排列

热度:97   发布时间:2024-01-19 05:54:43.0

题意:

在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");elseputs("THESE WINDOWS ARE CLEAN");scanf("%*s");}return 0;
} 


  相关解决方案