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:在自己的数据上很快阿,谁给组超时的

Posted by lookus at 2005-07-31 23:10:28 on Problem 2518
In Reply To:时限是不是太紧了,这样都TLE,过得程序快的就那两个阿 Posted by:lookus at 2005-07-31 23:07:27
> #include <iostream.h>
> #include <string.h>
> #include <algorithm>
> #define inf 20000000
> #define KB(i) (k&(1<<(i)))
> #define BIN(i) (1<<(i))
> int b[1<<16],v[1<<16],s[1<<16],min,sum;
> int a[]={51,102,204,816,1632,3264,13056,26112,52224};
> char str[20];
> int maxDFS(int k,int step)
> {
> 	return 0;
> }
> int dfs(int k,int dep)
> {
> 	if(b[k]!=-1)
> 		return b[k];
> 	if(v[k]!=dep)
> 		return 0;	
> 	int i,d=0;
> 	--dep;
> 	for(i=0;i<16;++i)
> 		if(k&BIN(i))
> 		{
> 			if(i-4>=0 && !KB(i-4))
> 				d += dfs((k|BIN(i-4))&(~BIN(i)),dep);
> 			if(i+4<16 && !KB(i+4))
> 				d += dfs((k|BIN(i+4))&(~BIN(i)),dep);
> 			if(i%4 != 0 && !KB(i-1))
> 				d += dfs((k|BIN(i-1))&(~BIN(i)),dep);
> 			if(i%4!=3 && !KB(i+1))
> 				d += dfs((k|BIN(i+1))&(~BIN(i)),dep);
> 		}
> 	return b[k] = d;
> }
> void minBFS(char c)
> {
> 	int k=0,r,f,i,j,d;
> 	for(i=0;i<16;++i)
> 		if(str[i]==c)
> 			k |= BIN(i);
> 	d = k;
> 	std::fill(v,v+(1<<16),inf);
> 	for(i=0;i<9;++i)
> 		v[a[i]]=0,s[i]=a[i];
> 	for(r=0,f=9;v[d]==inf;++r)
> 	{
> 		k = s[r];
> 		for(i=0;i<16;++i)
> 			if(k&BIN(i))
> 			{
> 				if(i-4>=0 && !KB(i-4))
> 				{
> 					j = ((k|BIN(i-4))&(~BIN(i)));
> 					if(v[j]==inf)
> 					{
> 						v[j] = v[k]+1;
> 						s[f++] = j;
> 					}
> 				}
> 				if(i+4<16 && !KB(i+4))
> 				{
> 					j = ((k|BIN(i+4))&(~BIN(i)));
> 					if(v[j]==inf)
> 					{
> 						v[j] = v[k]+1;
> 						s[f++] = j;
> 					}
> 				}
> 				if(i%4 != 0 && !KB(i-1))
> 				{
> 					j = ((k|BIN(i-1))&(~BIN(i)));
> 					if(v[j]==inf)
> 					{
> 						v[j] = v[k]+1;
> 						s[f++] = j;
> 					}
> 				}
> 				if(i%4!=3 && !KB(i+1))
> 				{
> 					j = ((k|BIN(i+1))&(~BIN(i)));
> 					if(v[j]==inf)
> 					{
> 						v[j] = v[k]+1;
> 						s[f++] = j;
> 					}
> 				}
> 			}
> 	}
> 	if(min < v[d])
> 		return ;
> 	std::fill(b,b+(1<<16),-1);
> 	for(i=0;i<9;++i)
> 		b[a[i]] = 1;
> 	k = dfs(d,v[d]);
> 	if(min == v[d])
> 		sum += k;
> 	else
> 	{
> 		min = v[d];
> 		sum = k;
> 	}
> }
> 
> void minStep()
> {
> 	min = inf;
> 	minBFS('A');
> 	minBFS('B');
> 	minBFS('C');
> 	minBFS('D');
> }
> void main()
> {
> 	char st[4];
> 	int i;
> 	while(cin>>str)
> 	{
> 		for(i=0;i<3;++i)
> 		{
> 			cin>>st;
> 			strcat(str,st);
> 		}
> 		minStep();
> 		cout<<min<<" "<<sum<<endl;
> 	}
> }

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