先写个暴搜+位运算的： 对于位运算的应用有所帮助,希望对于像偶一样的菜鸟有所帮助；
这里对与位运算的理解还是 i 到 a[4][4] 的转换：
举个例子吧： i=1 a[][]=
{0,0,0,0,
0 0 0 0 ,
0 0 0 0 ,
0 0 0 1} 至于详细的思路参考：http://blog.sina.com.cn/s/blog_63509b890100pm7b.html
View Code
//poj 1753
#include <iostream>
#define MAX 0x7ffffff
using namespace std;
int flip[16] = {0x13,0x27, 78,140,305,626,1252,2248,4880,8992,20032,35968,12544,29184,58368,51200};//分别对于十六个位置的翻一次的处理
int onepos[16] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
//一的位置处理
int main()
{
int sum=0,min=MAX;
char ch;
for(int i=0;i<16;i++)//求输入的综合即1的次数
{
cin>>ch;
if(ch=='w') sum+=onepos[i];
}
for(int i=0;i<65536;i++) //2^16 次进行枚举或暴搜
{
int tsum=sum,count=0;
for(int j=0;j<16;j++)
{
if(i&onepos[j])
//这里可能不好理解，主要是判断第i位置是否翻转，i就是枚举的翻转的状态
{
count++;
tsum^=flip[j];
}
}
if(tsum==0||tsum==65535)
{
if(min>count)
min=count;
}
}
if(min==MAX) cout<<"Impossible"<<endl;
else cout<<min<<endl;
return 0;
}
dfs 版
View Code
#include<stdio.h>
int least=17;
int cur=0,p[17];
void dfs(int cur,int dept,int base)
{
if(cur==0||cur==65535)
{
if(least>dept)
{
least = dept; return ;
}
}
if(least>17) return ;
for(int i=base;i<16;i++)
{
int x=i/4,y=i%4;
int tcur=cur,t=p[i]; tcur^=t;
if(x>0) {t=p[4*(x-1)+y];tcur^=t;}
if(x<3) {t=p[4*(x+1)+y];tcur^=t;}
if(y>0) {t=p[4*(x)+y-1];tcur^=t;}
if(y<3) {t=p[4*(x)+y+1];tcur^=t;}
dfs(tcur,dept+1,i+1);
}
}
int main()
{
char str[5];
for(int i=0;i<16;i++) p[i]=1<<i;
for(int i=0;i<4;i++)
{
scanf("%s",str);
for(int j=0;j<4;j++)
if(str[j]=='b') cur+=p[i*4+j];
}
dfs(cur,0,0);
if(least>=17) puts("Impossible");
else printf("%d\n",least);
return 0;
#include<stdio.h>
int p[17],least=17;
void dfs(int cur,int dept,int base)
{
if(cur==0||cur==65535)
{
if(least>dept) least=dept;
return ;
}
if(least>17) return ;
for(int i=base;i<16;i++)
{
int x=i/4,y=i%4;
int t=p[i],tcur=cur;
if((t&tcur)==0) tcur+=t;else tcur-=t;
if(x>0) {t=p[4*(x-1)+y];if((t&tcur)==0) tcur+=t;else tcur-=t;}
if(x<3) {t=p[4*(x+1)+y];if((t&tcur)==0) tcur+=t;else tcur-=t;}
if(y>0) {t=p[4*(x)+y-1];if((t&tcur)==0) tcur+=t;else tcur-=t;}
if(y<3) {t=p[4*(x)+y+1];if((t&tcur)==0) tcur+=t;else tcur-=t;}
dfs(tcur,dept+1,i+1);
}
}
int main()
{
int cur=0;
char str[5];
for(int i=0;i<16;i++) p[i]=1<<i;
for(int i=0;i<4;i++)
{
scanf("%s",str);
for(int j=0;j<4;j++)
if(str[j]=='b') cur+=p[i*4+j];
}
dfs(cur,0,0);
if(least>=17) puts("Impossible");
else printf("%d\n",least);
}
poj 2965 The Pilots Brothers' refrigerator 和这道题差不多
View Code
#include<stdio.h>
#include<string.h>
int p[17],least=17;
struct node
{
int xl,yl;
void init(int &_x,int &_y)
{
xl=_x;yl=_y;
}
}curxy[17],bestxy[17];
void dfs(int cur,int dept,int base)
{
if(cur==0)
{
if(least>dept)
{
least=dept;
memcpy(bestxy,curxy,sizeof(curxy));
}
return ;
}
if(least>17) return ;
for(int i=base;i<16;i++)
{
int x=i/4,y=i%4;
int t=p[i],tcur=cur;
if((t&tcur)==0) tcur+=t;else tcur-=t;
for(int j=0;j<4;j++)
{
t=p[4*j+y];
if((t&tcur)==0) tcur+=t;else tcur-=t;
}
for(int j=0;j<4;j++)
{
t=p[4*x+j];
if((t&tcur)==0) tcur+=t;else tcur-=t;
}
curxy[dept].init(x,y);
dfs(tcur,dept+1,i+1);
}
}
int main()
{
int cur=0;
char str[5];
for(int i=0;i<16;i++) p[i]=1<<i;
for(int i=0;i<4;i++)
{
scanf("%s",str);
for(int j=0;j<4;j++)
if(str[j]=='+') cur+=p[i*4+j];
}
dfs(cur,0,0);
printf("%d\n",least);
for(int i=0;i<least;i++)
printf("%d %d\n",bestxy[i].xl+1,bestxy[i].yl+1);
}