随笔-72  评论-126  文章-0  trackbacks-0
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ǎ崽 阅读(1027) 评论(5)  编辑 收藏 引用

评论:
# re: hdoj1430~~魔板~~解题报告 2009-02-27 18:12 | fdar
楼主八数码也写了啊。
那能不能把八数码的A-STAR算法也写个解题报告啊  回复  更多评论
  
# re: hdoj1430~~魔板~~解题报告 2009-02-27 20:37 | shǎ崽
@fdar


呵呵,好的  回复  更多评论
  
# re: hdoj1430~~魔板~~解题报告 2009-04-03 22:42 |
能把代码提供出来吗,预处理还是不太懂  回复  更多评论
  
# re: hdoj1430~~魔板~~解题报告 2009-04-03 22:45 |
预处理的转换明白了,但预处理怎么应来解决字典序还是不太懂,请再讲明白,谢谢!  回复  更多评论
  
# re: hdoj1430~~魔板~~解题报告 2009-04-05 17:48 | shǎ崽
好的  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理