The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1077 八数码问题

瞻仰下八数码,可惜效率还不行啊,看到那么多0MS的,打击啊。。。这题如果要0MS,必须是A*吧,呵呵 可惜还不会呀。。。

#include<iostream>
#include
<algorithm>
#include
<cstring>
using namespace std;

struct node
{
    
int dir;
    
int pre;
    
int step;
    
char x[10];
}
l[400000];


char x[15];
char ansx[15]="123456780";
int perm[] = {1,1,2,6,24,120,720,5040,40320};//n! 
int d[] = {-1,-313};//四个方向的下标变换,左上右下。
bool move[][4= {0,0,1,11,0,1,11,0,0,10,1,1,11,1,1,11,1,0,10,1,1,01,1,1,01,1,0,0}
//各个位置的可行变换
int v[362881];//数组判重
int hash()//用逆序数和变进制进行hash 

    
int h = 0
    
for(int i = 1;i<9;i++)
    

        
int count = 0
        
for(int j=0;j<i;j++
            
if(x[j] > x[i])count ++
        h 
+= count * perm[i]; 
    }
 
    
return h; 
}
 

void input()
{

    
char t[5];
    
for(int i=0;i<9;i++)
    
{
        scanf(
"%s",t);
        x[i]
=t[0];
        
if(x[i]=='x')
            x[i]
='0';
    }

}



int pos;
void search(char x[])
{
    
for(int i=0;i<9;i++)
        
if(x[i]=='0')
        
{
            pos
=i;
            
break;
        }


}

char ans[4000000]={0};
void GetDir(int h)
{
    memset(ans,
0,sizeof(ans));
    
int i;
    
int n=l[h].step;
    
for(i=n;i>=1;i--)
    
{
        
        
if(l[h].dir==0)
            ans[i]
='l';
        
else if(l[h].dir==1)
            ans[i]
='u';
        
else if(l[h].dir==2)
            ans[i]
='r';
        
else if(l[h].dir==3)
            ans[i]
='d';
        h
=l[h].pre;
    }

}




int main()
{
    

    
int head,tail;
    memset(v,
0,sizeof(int)*362881);
    head
=tail=1;
    input();
    
//
    int code=hash();
    v[code]
=1;
    l[head].step
=0;
    l[head].pre
=-1;
    strcpy(l[head].x,x);
    
//initial

    
while(head<=tail)
    
{
        
if(strcmp(l[head].x,ansx)==0)
            
break;//此时head为所求解
        search(l[head].x);
        
for(int i=0;i<4;i++)
        
{
            
if(move[pos][i]==0)
                
continue;
            strcpy(x,l[head].x);
            
int np=pos+d[i];
            swap(x[pos],x[np]);
            
int code=hash();
            
if(!v[code])
            
{
                
                tail
++;
                v[code]
=1;
                l[tail].step
=l[head].step+1;
                l[tail].pre
=head;
                l[tail].dir
=i;
                strcpy(l[tail].x,x);
            }


        }

        head
++;
    }

    
if(head>tail)
        printf(
"unsolvable\n");
    
else
    
{
        GetDir(head);
        printf(
"%s\n",ans+1);
    }



    
return 0;
}



另外那个十五数码,能用程序搞出来么?

这里的哈希函数是用能对许多全排列问题适用的方法。取n!为基数,状态第n位的逆序值为哈希值第n位数。对于空格,取其(9-位置)再乘以8!。例如,1 3 7 2 4 6 8 5 8 的哈希值等于:
0*0! + 0*1! + 0*2! + 2*3! + 1*4! + 1*5! + 0*6! + 3*7! + (9-8)*8! = 55596 <9!
 具体的原因可以去查查一些数学书,其中1 2 3 4 5 6 7 8 9 的哈希值是0 最小,8 7 6 5 4 3 2 1 0 的哈希值是(9!-1)最大,而其他值都在0 到 (9!-1) 中,且均唯一。

posted on 2010-05-03 19:26 abilitytao 阅读(1783) 评论(6)  编辑 收藏 引用

评论

# re: POJ 1077 八数码问题 2010-05-03 21:37 abilitytao

@TimTopCoder
thx, maybe I have to learn the A* algorithm for a deep research..  回复  更多评论   

# re: POJ 1077 八数码问题 2010-05-03 22:08 aaa

八数码问题这样搞,
这个算法也太傻了吧。  回复  更多评论   

# re: POJ 1077 八数码问题 2010-05-03 23:46 abilitytao

@aaa
非常SB!呵呵  回复  更多评论   

# re: POJ 1077 八数码问题 2010-05-04 11:32 丽可酷

八数码问题这样搞  回复  更多评论   

# re: POJ 1077 八数码问题 2010-07-28 14:17 knight4hy

看了半天发现是非常简单的广搜,可我是搜A*进来的  回复  更多评论   

# re: POJ 1077 八数码问题[未登录] 2010-07-28 22:23 abilitytao

@knight4hy
那你可以继续搜 直到搜到我写A*的那篇。。。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理