與POJ 1753類似，但是需要加點優化，這里主要使用了位運算的方法。
#include<cstdio>
#include<cstring>
#define g(x,y) (((x-1)<<2)+y)
using namespace std;
int a,d;
int ansn,ans;
void f(int i,int &x,int &y)
{
x=i/4+1;
y=i%4;
if(i%4==0)
{
x--;
y=4;
}
}
void handle(int &r,int x,int y)
{
for(int i=1;i<=4;i++)
{
r^=(1<<g(x,i));
r^=(1<<g(i,y));
}
r^=(1<<g(x,y));
}
void dfs(int last,int have)
{
if(have>=ansn)
return;
int r(a);
for(int i=1;i<=16;i++)
if(d&(1<<i))
{
int x,y;
f(i,x,y);
handle(r,x,y);
}
if(r==0)
{
ansn=have;
ans=d;
}
for(int i=last+1;i<=16;i++)
{
d=(d|(1<<i));
dfs(i,have+1);
d=(~((~d)|(1<<i)));
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
a=0;
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
char t;
scanf("%c",&t);
if(t=='+')
a=(a|(1<<g(i,j)));
else
a=(~((~a)|(1<<g(i,j))));
}
getchar();
}
ansn=0x7f7f7f7f;
d=0;
dfs(0,0);
printf("%d\n",ansn);
for(int i=1;i<=16;i++)
if(ans&(1<<i))
{
int x,y;
f(i,x,y);
printf("%d %d\n",x,y);
}
return 0;
}
posted on 2011-07-31 09:39
lee1r 閱讀(188)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索