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