Detail of message

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

时限是不是太紧了，这样都TLE，过得程序快的就那两个阿

Posted by lookus at 2005-07-31 23:07:27 on Problem 2518

#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:

Re:在自己的数据上很快阿，谁给组超时的 (2375) lookus 2005-07-31 23:10:28
- 查查越界之类的问题吧，说不定是那个 (0) frkstyc 2005-07-31 23:12:42
  - Re:不会是越界吧，而且我也想不出哪儿可能，再说是TLE (0) lookus 2005-07-31 23:20:03
    - 假如你局部越界覆盖了栈里面的东西的话，要TLE也不是很难 (0) frkstyc 2005-07-31 23:22:34
      - Re:我刚才把数组开大了一倍，还是TLE，是不是这个算法不行啊 (0) lookus 2005-07-31 23:30:50
        Re:刚才试了一下，只那个BFS就超了，ft (0) lookus 2005-07-31 23:32:51
        你有没有判重啊 (0) frkstyc 2005-07-31 23:33:53
修改一下，减小常数吧，感觉你的常数不小 (2375) frkstyc 2005-07-31 23:33:16
200submit/113tle (2375) sunmoonstar_love 2005-07-31 23:35:36
先把每种状态到达目标需要的步数算出来,然后沿步数减小的路径DFS (2375) xfxyjwf 2005-07-31 23:35:39
- 总共的状态也就1820种...考试的时候居然一点思路都没有... (0) xfxyjwf 2005-07-31 23:36:50
  - 不是没思路，是最后时刻才想起 (0) frkstyc 2005-07-31 23:46:35
- 想想，觉得DFS也是浪费时间，为什么不到过来推？一次BFS爽了 (0) frkstyc 2005-08-01 01:36:53
  - xf写一个看看，不搞了 (0) frkstyc 2005-08-01 01:37:38
    - 一次BFS好像不行吧? (0) xfxyjwf 2005-08-01 01:43:26
      - 从win的位置往回推出其他位置，顺道就把方法数什么的都算好了吧？ (0) frkstyc 2005-08-01 01:44:18
        好像可以,我试试 (0) xfxyjwf 2005-08-01 01:50:40
      - 不过你较真的话，算9次好了，9个win position (0) frkstyc 2005-08-01 01:44:58
    - 果然一次BFS就全部搞定了 (0) c0500448242 2005-08-01 01:55:34
      - 两个笨蛋…… (0) frkstyc 2005-08-01 01:57:54
        ... (0) xfxyjwf 2005-08-01 01:58:30
        你不算，只算我一个好了 (0) frkstyc 2005-08-01 02:00:25
        考试的时候想不出来也是没办法的事. (0) xfxyjwf 2005-08-01 02:02:30
Re:就是个BFS，还是TLE阿code (1874) lookus 2005-08-01 03:19:03
- 一次过全部算好，然后查表…… (2102) frkstyc 2005-08-01 03:26:34

Post your reply here:

User ID:
Password:
Title:

Content:

> #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;
> 	}
> }

Home Page Go Back To top