| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
折腾了半天,终于不超时了,对位运算也有了更深入的了解,贴上代码,纪念一下poj第21题#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
class cwj
{
public:
int state;
int xl;
int pre;
int l;
};
bool tt[100000];
int p[20];
int main()
{
queue<cwj> q;
cwj aaa,bbb;
int i,j,ll,x,k;
char s[5][10];
int b=0;
bool ch;
p[0]=1;
for(i=1;i<=16;i++)
p[i]=2*p[i-1];
for(i=0;i<4;i++)
{
gets(s[i]);
for(j=0;j<4;j++)
{
if(s[i][j]=='+')
{
b+=p[i*4+j];
}
}
}
tt[b]=1;
for(i=0;i<16;i++)
{
aaa.state=b;
aaa.xl=p[i];
aaa.pre=i;
aaa.l=1;
x=i/4;
aaa.state^=p[x*4];
aaa.state^=p[x*4+1];
aaa.state^=p[x*4+2];
aaa.state^=p[x*4+3];
x=i%4;
aaa.state^=p[x];
aaa.state^=p[x+4];
aaa.state^=p[x+8];
aaa.state^=p[x+12];
aaa.state^=p[i];
if(!tt[aaa.state])
{
q.push(aaa);
tt[aaa.state]=1;
}
}
while(q.empty()!=true)
{
bbb=q.front();
ll=q.front().l;
ch=false;
if(bbb.state==0)
ch=true;
if(ch)
{
break;
}
else
{
aaa.l=bbb.l+1;
for(i=bbb.pre+1;i<16;i++)
{
aaa.xl=bbb.xl;
aaa.xl+=p[i];
aaa.pre=i;
aaa.state=bbb.state;
x=i/4;
aaa.state^=p[x*4];
aaa.state^=p[x*4+1];
aaa.state^=p[x*4+2];
aaa.state^=p[x*4+3];
x=i%4;
aaa.state^=p[x];
aaa.state^=p[x+4];
aaa.state^=p[x+8];
aaa.state^=p[x+12];
aaa.state^=p[i];
if(!tt[aaa.state])
{
q.push(aaa);
tt[aaa.state]=1;
}
}
q.pop();
}
}
cout<<ll<<endl;
for(i=0;i<16;i++)
{
k=bbb.xl;
k&=p[i];
if(k!=0)
printf("%d %d\n",i/4+1,i%4+1);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator