huyilei1114
huyilei1114
采纳率0%
2016-06-14 11:35

做八数码时遇到的一个小问题,百思不得其解,求助各位!!!

10

#include
#include
#include
using namespace std;
int mark;
int shift[9][9];//shift[0][1]表示x在1位置上的偏移
int factorial[9]={
1,1,2,6,24,120,720,5040,40320
};//factorial[3]=3!
struct maze{
int f,g,h;
int A[9];
int pos[200];//某个数(下标)的位置
int hash;
int prev;
int direction;
bool operator <(const maze &m1) const
{
return f>m1.f;
}
public:
maze(){};
int get_hash(){
int sum=0;
int temp;
for(int i=0;i if(A[i]=='x'){
sum+=(9-i)*factorial[8];
continue;
}
temp=0;
for(int j=0;j if(A[j]>A[i]&&A[j]!='x') temp++;
}
sum+=temp*factorial[i];
}
return sum;
}//康拓展开(n位全排列唯一)

maze(int temp[]){
    for(int i=0;i<9;i++){
        A[i]=temp[i];
        pos[temp[i]]=i; 
    }
    f=g=h=0;
    for(int i=0;i<9;i++){
        if(A[i]=='x') h+=shift[0][i];
        else h+=shift[A[i]][i];
    }
    prev=-1;
    hash=get_hash();
    direction=-1;
}


void PrintItSelf(){
    if(direction==0) cout<<"向上"<<endl;
    else if(direction==1) cout<<"向下"<<endl;
    else if(direction==2) cout<<"向左"<<endl;
    else if (direction==3) cout<<"向右"<<endl;
    for(int i=0;i<9;i++){
        if(i%3==2){
            if(A[i]!='x') cout<<A[i]<<endl;
            else cout<<'x'<<endl;
        }
        else{
            if(A[i]!='x') cout<<A[i]<<" ";
            else cout<<'x'<<" ";
        }
    }
}

};

priority_queue openlist;
int vis[500000];
int dir[]={
-3,3,-1,1//上下左右
};
//int problem[]={2,8,3,1,6,4,7,'x',5};
//int target[]={1,2,3,8,'x',4,7,6,5};
// 2 8 3 1 6 4 7 x 5
// 1 2 3 8 x 4 7 6 5

int problem[9]={2,3,4,1,5,'x',7,6,8};
int target[9]={1,2,3,4,5,6,7,8,'x'};
maze M[500000];

void calculate(maze &m1){
if(m1.prev!=-1) m1.g=M[m1.prev].g+1;
m1.f=m1.g+m1.h;
}

int check(int m,int i){//判断此处是否在九宫格内
int row=m/3;
int col=m%3;
switch(i){
case 0:row--;break;
case 1:row++;break;
case 2:col--;break;
case 3:col++;break;
}
if(row>=0&&row<=2&&col>=0&&col<=2) return 1;
return 0;
}

void Astar(){
maze m1=maze(problem);
calculate(m1);
openlist.push(m1);
while(openlist.size()){
maze Temp=openlist.top();openlist.pop();
vis[Temp.hash]=1;
if(!Temp.h){//打印路径
int steps=Temp.f;
printf("第%d步\n",steps--);
Temp.PrintItSelf();
printf("\n");
int now=Temp.prev;
while(now!=-1){
if(steps==0) printf("初始状态 ",steps--);
else printf("第%d步 ",steps--);
M[now].PrintItSelf();
printf("\n");
now=M[now].prev;
}
break;
}
int m=Temp.pos['x'];//m是x的位置
for(int i=0;i<4;i++){
int p=m+dir[i];//p是待交换的位置

## if(p>=0&&p<=8){//最初使用的判断导致错误,但是用check函数却会报错

            int B[9];
            for(int k=0;k<9;k++) B[k]=Temp.A[k];
            int mid=B[p];B[p]='x';B[m]=mid;
            maze Pmaze=maze(B);
            if(vis[Pmaze.hash]==1) continue;
            else if(vis[Pmaze.hash]==0){
                if(Temp.g+1<Pmaze.g){
                    Pmaze.g=Temp.g+1;
                    Pmaze.f=Pmaze.g+Pmaze.h;
                    Temp.direction=i;
                    M[mark]=Temp;
                    Pmaze.prev=mark++;
                }
            }
            else{
                Temp.direction=i;
                M[mark]=Temp;
                Pmaze.prev=mark++;
                calculate(Pmaze);
                openlist.push(Pmaze);
                vis[Pmaze.hash]=0;
            }
        }
    }
}

}

int verse(int a[9]){
int sum=0;
for(int i=0;i if(a[i]=='x') continue;
for(int j=0;j {
if(a[j]>a[i]&&a[j]!='x') sum++;
}
}
return sum%2;
}//逆序数奇偶性相同有解,不同无解

void ProcessShift(){
maze m1=maze(problem);
maze m2=maze(target);
int a=m2.pos['x']/3;
int b=m2.pos['x']%3;
for(int j=0;j<9;j++){
int row3=j/3;
int column3=j%3;
shift[0][j]=abs(a-row3)+abs(b-column3);
}
for(int i=1;i<9;i++){
int row1=m2.pos[i]/3;
int column1=m2.pos[i]%3;
for(int j=0;j<9;j++){
int row2=j/3;
int column2=j%3;
shift[i][j]=abs(row1-row2)+abs(column1-column2);
}
}
}//预处理偏移

int main(){
mark=0;//存储九宫格,用来打印路径
memset(vis,-1,sizeof(vis));
ProcessShift();
if(verse(problem)!=verse(target)) cout<<"无法解决"<<endl;
else Astar();
return 0;
}

最初使用的判断导致错误,
第七步显然不能左移到第八步的位置
但是用check函数却会报错,百思不得其解!!

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • ZSGG_ACM ZSGG_ACM 5年前

    这种问题建议你自己调试下,自己找的错误,总比别人帮你找的印象深刻

    点赞 1 评论 复制链接分享
  • u011606457 _1_1_7_ 5年前

    数组下标越界了吗?
    具体是报什么错误

    点赞 评论 复制链接分享

为你推荐