Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:枚举最低79ms,还能减少吗?

Posted by renhuan0737 at 2010-10-13 21:16:55 on Problem 1753
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");
     return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator