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 |
Re:枚举最低79ms,还能减少吗?In Reply To:枚举最低79ms,还能减少吗? Posted by:windows8 at 2009-11-18 19:17:46 > //从翻转1个循环到16个,再循环翻转顺序 > #include<stdio.h> > #include<string.h> > #include<algorithm> > int t[16],a[16]; > void trans(int n) > {a[n]^=1; > if(n>3) > a[n-4]^=1; > if(n<12) > a[n+4]^=1; > if(n%4) > a[n-1]^=1; > if(n%4!=3) > a[n+1]^=1; > } > bool ok() > {int i,s=0; > for(i=0;i<16;i++) > s+=a[i]; > if(!s||s==16) > return 1; > return 0; > } > int main() > {char s[16]; > int i,j,k; > for(i=0;i<4;i++) > {scanf("%s",s); > for(j=0;j<4;j++) > if(s[j]=='w') > a[i*4+j]=t[i*4+j]=1; > } > if(ok()) > {puts("0");return 0;} > for(i=1;i<17;i++) > {memset(s,0,sizeof(s)); > for(j=0;j<i;j++) > s[15-j]=1; > do{ > memcpy(a,t,sizeof(a)); > for(k=0;k<16;k++) > if(s[k]) > trans(k); > if(ok()) > { > printf("%d\n",i); > return 0; > } > }while(std::next_permutation(s,s+16)); > } > puts("Impossible"); > } 没有啊,我也是枚举的,0ms. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator