http://acm.hdu.edu.cn/showproblem.php?pid=1430整整花了我两天时间。。。
唉。。。本来以为是很简单的
写完八数码后知道了逆序数一个hash函数
以为写这题也可以这样做
很简单的写好后提交结果是TLE。。。唉，数据量太大了。。。
虽然说最多只有40320个状态，但由于in文件太大，有40KB，会导致超时。
所以请教了高杰之后知道可以用双向广搜处理。
这样时间就少了很多很多
应为广搜到后边状态是指数级别增长的
但是写阿写，总是写不对，关键是字典序最小的那过很难处理，看了高杰的代码后还不知所然。。
昨天晚上请教了linle大牛，他是这题时间最短的人，只用了15MS，用双向广搜至少都要2000MS+
他一语道破玄机，“预处理”，所有状态到12345678全部先处理出来
于是我就在想预处理之后能怎么做。。
先预处理说所有状态到12345678的字典序最小的最优解
今天终于想出来了。每个初始状态都可以转化成12345678
比如拿
47586312
87654321来说
可以转化成
12345678
42531687
接下来就简单了
根据预处理出来的路径打印。。。
#include<stdio.h>
#include<string>
#define Max 40321
char num[Max][9];
int hash[Max];
int father[Max];
int ku[] = {1,1,2,6,24,120,720,5040};
char act[Max];
int hash_code(char *a)
{
int i,j,cnt,sum=0;
for(i=0;a[i];i++)
{
cnt = 0;
for(j=0;j<i;j++)
{
if(a[j]>a[i])
cnt ++;
}
sum += cnt*ku[i];
}
return sum;
}
void change(char *a,char *b,int s)
{
int i;
char c;
switch (s)
{
case 0:
strcpy(a,b);
strrev(a);
return ;
case 1:
a[0] = b[3];
for(i=0;i<3;i++)
a[i+1] = b[i];
a[7] = b[4];
for(i=5;i<=7;i++)
a[i-1] = b[i];
a[8] = 0;
return ;
case 2:
strcpy(a,b);
c = a[5];
a[5] = a[2];
a[2] = a[1];
a[1] = a[6];
a[6] = c;
return ;
}
}
void bfs()
{
int head,tail,i,key;
head = tail = 0;
char next[9];
for(i=0;i<8;i++)
num[0][i] = i+'1';
num[0][i] = 0;
memset(hash,-1,sizeof(hash));
hash[hash_code(num[0])] = 0;
while(head <= tail)
{
for(i=0;i<3;i++)
{
change(next,num[head],i);
key = hash_code(next);
if(hash[key]==-1)
{
tail ++;
hash[key] = tail;
strcpy(num[tail],next);
act[tail] = 'A' + i;
father[tail] = head;
}
}
head ++;
}
tail = 0;
}
int main()
{
char start[9],end[9],ans[100];
int pos[9],i,key;
bfs();
while(scanf("%s%s",start,end)==2)
{
for(i=0;i<8;i++)
pos[start[i]-'1'] = i;
for(i=0;i<8;i++)
end[i] = pos[end[i]-'1'] +'1';
end[8] = 0;
key = hash[hash_code(end)];
i = 0;
while(key)
{
ans[i++] = act[key];
key = father[key];
}
ans[i] = 0;
strrev(ans);
puts(ans);
}
return 0;
}
posted on 2009-02-27 16:41
shǎ崽 阅读(1155)
评论(5) 编辑 收藏 引用