本文主要是介绍poj 2965 The Pilots Brothers' refrigerator 枚举+组合 暑假第二题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
其实和 poj 1753样,甚至更简单,套用1753代码打的,并优化了一部分;
具体参考:http://blog.csdn.net/sholck222/article/details/46695087
但在这道题中,可能限制时间交紧,相同代码提交两次才过,第一次超时,第二次险过,953ms;
这道题还有其他解法,如高斯解法,枚举+dfs,这两份代码及简析明天会发上来
枚举+组合的代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[5][5];
char b[25];
char c[25];
int num[25];
int guanlian=0;
int check=0;
int tell()//判断是否全关上
{int i,j;int k1=1;for(i=0; i<16; i++){if(b[i]=='0')k1=0;}if(k1==0)//没关上return -1;elsereturn 0;//关上
}
void gaibian(int p)
{if(b[p]=='+')b[p]='0';//关elseb[p]='1';//开
}
void gaibian2(int p)
{if(b[p]=='1')b[p]='0';//关elseb[p]='1';//开
}
int fanzhuan()
{int j;for(j=0; j<guanlian; j++){int p=num[j];int x=p/4;int y=p%4;int i;int k1=p-y;gaibian2(p);for(i=k1; i<=k1+3; i++){gaibian2(i);}int k2=p-4*x;for(i=0; i<4; i++){gaibian2(k2+i*4);}}if(tell()==0)return 1;//已全部关上elsereturn -1;//没关上
}
void huanyuan()
{int i,j;for(i=0;i<16;i++){b[i]=c[i];}
}
void select_com(int l,int p)
{int i;if(l==guanlian){int g=fanzhuan();if(g==1){check=1;printf("%d\n",guanlian);//cout<<guanlian<<endl;for(i=0;i<guanlian;i++){int x=num[i]/4;int y=num[i]%4;printf("%d %d\n",x+1,y+1);//cout<<x+1<<' '<<y+1<<endl;}return ;}else{huanyuan();}}for(i=p; i<16; i++){if(check==0){num[l]=i;select_com(l+1,i+1);}}
}int main()
{int start=0;int i,j;for(i=0; i<4; i++){for(j=0; j<5; j++) // !!!!!!!!!!!!!!!! j == 4时输入 '\n'{scanf("%c",&a[i][j]);if (j == 4) continue; // !!!!!!!!!!b[start]=a[i][j];gaibian(start);c[start]=b[start];start++;}}int m=1;while(m<=16){guanlian=m;select_com(0,0);if(check==1)break;m++;}check=0;return 0;
}
这篇关于poj 2965 The Pilots Brothers' refrigerator 枚举+组合 暑假第二题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!