首页 > 其他 > 详细

poj 1753

时间:2014-05-21 21:00:33      阅读:416      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
题意:给定4*4的矩形 由16个矩形组成 上面由w或b 组成 背面相反 每次能翻转3到5个小矩形 求最少的步数能使矩形全部为w或全部为b
思路:有固定的2^16次方个状态 也就是矩形的子集的个数 枚举所有的状态就可以了

#include<iostream> using namespace std; int arr[26]; int result[26]; int b; int n; void slip(int i,int *now)//翻转矩形 { now[i]=!now[i]; int x=i/4; int y=i%4; if(y<3) now[i+1]=!now[i+1]; if(y>0) now[i-1]=!now[i-1]; if(x>0) now[i-4]=!now[i-4]; if(x<3) now[i+4]=!now[i+4]; } bool b_w(int *now)//判断是否全为白色或全为黑色 { for(int i=0;i<16;i++) if(now[i]!=now[0]) return false; return true; } void funtion() { int i; int now[26]; for(i=0;i<16;i++) now[i]=arr[i]; for(i=0;i<n;i++) slip(result[i],now); if(b_w(now)) { b=1; cout<<n<<endl; return ; } } void dfs(int start,int num)//搜索 枚举所有的子集和 { if(b) return ; if(num>=n) { funtion(); return ; } int i; for(i=start;i<=16-(n-num);i++) { result[num]=i; dfs(i+1,num+1); } } int main() { int i,j; char str[11]; for(i=0;i<4;i++) { cin>>str; for(j=0;j<4;j++) if(str[j]==w) arr[i*4+j]=1; else arr[i*4+j]=0; } b=0; for(i=0;i<=16;i++) { n=i; dfs(0,0); if(b) break; } if(!b) cout<<"Impossible"<<endl; }
bubuko.com,布布扣

 

poj 1753,布布扣,bubuko.com

poj 1753

原文:http://www.cnblogs.com/zhangdashuai/p/3739559.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!