hdu 1043(八數碼問題) -开发者知识库

hdu 1043(八數碼問題) -开发者知识库,第1张

<span style="font-family: Arial, Helvetica, sans-serif;">題意:省略</span>

 解題思路:針對八數碼問題,如果x往左或往右走,是不會改變逆序數大小的,且往上或往下走只有三種情況,討論往下走,如果與x交換的數是ai,則要判斷的是a(i-1),a(i-2)與ai的關系.

                 只會出現四種情況,a(i-1)>ai,a(i-2)>ai;逆序對數在原來的基礎上+2

 a(i-1)<ai,a(i-2)>ai;逆序對數在原來的基礎上不變

                                                 a(i-1)>ai,a(i-2)<ai;逆序對數在原來的基礎上不變

 a(i-1)<ai,a(i-2)<ai;逆序對數在原來的基礎上-2

 針對上述四種情況,逆序數的初始值為0,則經過各種變換逆序數為偶數,則若一種狀態逆序數為奇數,始不可能的。且在保存狀態時利用康托展開:X=an*(n-1)! an-1*(n-2)! ... ai*(i-1)! ... a2*1! a1*0! (ai為某個數對應的逆序對數,達到狀態壓縮)。

 這里要利用反向的思維,通過最終狀態去bfs所有狀態。          

 




                 只會出現四種情況,a(i-1)>ai,a(i-2)>ai;逆序對數在原來的基礎上+2

 a(i-1)<ai,a(i-2)>ai;逆序對數在原來的基礎上不變

                                                 a(i-1)>ai,a(i-2)<ai;逆序對數在原來的基礎上不變

 a(i-1)<ai,a(i-2)<ai;逆序對數在原來的基礎上-2

 針對上述四種情況,逆序數的初始值為0,則經過各種變換逆序數為偶數,則若一種狀態逆序數為奇數,始不可能的。且在保存狀態時利用康托展開:X=an*(n-1)! an-1*(n-2)! ... ai*(i-1)! ... a2*1! a1*0! (ai為某個數對應的逆序對數,達到狀態壓縮)。

 這里要利用反向的思維,通過最終狀態去bfs所有狀態。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;
#define MAXN 50
#define MAZE 600000
typedef struct node{
    char str[50];
    int nx[9];
    int num,hashnum,xind;
    node();
    node(char *ss,int nu,int hanu,int *nnx){
        strcpy(str,ss);
        num = nu;
        hashnum = hanu;
        for(int i=0;i<9;  i){
            nx[i] = nnx[i];
        }
    }
    void charstr(){
        int tmp = 0;
        int tmpc;
        int tmpnum = num;
        tmpc = 9;
        int zflag = 0;
        while(num){
            zflag = num;
            str[tmpc -1] = '0'  zflag;
            if(zflag==9)
                tmp = tmpc - 1;
            num/=10;
            --tmpc;
        }
        num = tmpnum;
        xind = tmp;
        //return tmp;
    }
};
queue<node>q;
int path[MAZE];
int nx[9];
int pa[MAZE],ans[MAZE];
bool vis[MAZE];
char nows[MAXN];
int cnt;
int p[]={1,1,2,6,24,120,720,5040,40320};
int pw[] = {100000000,10000000,1000000,100000,10000,1000,100,10,1};
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int goal;
void prepro(){
    cnt = 0;
    int len = (int)strlen(nows);
    for(int i=0;i<len;  i){
        if(nows[i]==32)continue;
        if(nows[i]=='x')nows[i] = '9';
        nows[cnt  ] = nows[i];
    }
    nows[cnt] = 0;
}
void init(){
    memset(vis,false,sizeof(vis));
    memset(pa,-1,sizeof(pa));
}
int charhash(char *str){
    //就保證系數ai》=0&&ai<=(8 - i)
    int ans = 0,tmpc;
    int st = 0;
    for(int i=0;i<cnt;  i){
        //if(nows[i]=='x')continue;
        tmpc = 0;
        for(int j = i 1;j<cnt;  j){
            //  if(nows[j]=='x')continue;
            if(str[i]>str[j])tmpc  ;
        }
        nx[i] = tmpc;
        ans =tmpc*p[8-i];
        //st  ;
    }
    return ans;
}

int getnx(){
    int ans = 0;
    for(int i=0;i<cnt;  i){
        //if(nows[i]=='x')continue;
        if(nows[i]=='9')continue;
        for(int j=i 1;j<cnt;  j){
            // if(nows[j]=='x')continue;
            if(nows[i]>nows[j])
                ans  ;
        }
    }
    return ans;
}
int getnumber(){
    int   ans = 123456789;
    return ans;
}
//右 左 下 上
int gethash(char *str,int num,int dir,int xind,int nxind,node &no){
    int tmpcc;
    if(dir==0){
        
        num = num-p[8-xind]*no.nx[xind]  - p[8-nxind]*no.nx[nxind];
        tmpcc = no.nx[nxind];
        no.nx[nxind]=no.nx[xind] - 1;
        no.nx[xind] = tmpcc;
        num =p[8-xind]*no.nx[xind]    p[8-nxind]*no.nx[nxind];
    }
    if(dir==1){
        num = num-p[8-xind]*no.nx[xind]  - p[8-nxind]*no.nx[nxind];
        tmpcc = no.nx[nxind];
        no.nx[nxind]=no.nx[xind]   1;
        no.nx[xind] = tmpcc;
        num =p[8-xind]*no.nx[xind]    p[8-nxind]*no.nx[nxind];
    }
    
    if(dir==2){
        int ind1,ind2;
        ind1 = xind 1;
        ind2 = xind 2;
        int cc = 0;
        if(str[nxind]>str[ind1])cc  ;
        if(str[nxind]>str[ind2])cc  ;
        num = num-p[8-xind]*no.nx[xind]  - p[8-nxind]*no.nx[nxind];
        tmpcc = no.nx[nxind];
        no.nx[nxind]=no.nx[xind] - 3;
        no.nx[xind] = tmpcc cc;
        num =p[8-xind]*no.nx[xind]    p[8-nxind]*no.nx[nxind];
        if(str[nxind]<str[ind1]){
            num-=p[8-ind1];
            no.nx[ind1]--;
        }
        if(str[nxind]<str[ind2]){
            num-=p[8-ind2];
            no.nx[ind2]--;
        }
    }
    if(dir==3){
        int ind1,ind2;
        ind1 = xind-1;
        ind2 = xind-2;
        int cc = 0;
        if(str[nxind]>str[ind1])cc  ;
        if(str[nxind]>str[ind2])cc  ;
        num = num-p[8-xind]*no.nx[xind]  - p[8-nxind]*no.nx[nxind];
        tmpcc = no.nx[nxind];
        no.nx[nxind]=no.nx[xind]   3;
        no.nx[xind] = tmpcc-cc;
        num =p[8-xind]*no.nx[xind]    p[8-nxind]*no.nx[nxind];
        if(str[nxind]<str[ind1]){
            num =p[8-ind1];
            no.nx[ind1]  ;
        }
        if(str[nxind]<str[ind2]){
            num =p[8-ind2];
            no.nx[ind2]  ;
        }
        
    }
    return num;
}
//右 左 下 上
void restart(char *str,int num,int dir,int xind,int nxind,node &no){
    int tmpcc;
    if(dir==0){
        //        num = num-p[8-xind]*no.nx[xind]  - p[8-nxind]*no.nx[nxind]   p[8-xind]*(no.nx[nxind]-1)    p[8-nxind]*no.nx[xind];
        tmpcc = no.nx[xind];
        no.nx[xind]=no.nx[nxind]   1;
        no.nx[nxind] = tmpcc;
    }
    if(dir==1){
        //        num = num-p[8-xind]*no.nx[xind]  - p[8-nxind]*no.nx[nxind]   p[8-xind]*(no.nx[nxind] 1)    p[8-nxind]*no.nx[xind];
        tmpcc = no.nx[xind];
        no.nx[xind]=no.nx[nxind] - 1;
        no.nx[nxind] = tmpcc;
        
    }
    
    if(dir==2){
        int ind1,ind2;
        ind1 = xind 1;
        ind2 = xind 2;
        int cc = 0;
        if(str[nxind]>str[ind1])cc  ;
        if(str[nxind]>str[ind2])cc  ;
        //        num = num-p[8-xind]*no.nx[xind]  - p[8-nxind]*no.nx[nxind]   p[8-xind]*(no.nx[nxind]-2)    p[8-nxind]*(no.nx[xind] cc);
        tmpcc = no.nx[xind];
        no.nx[xind]=no.nx[nxind]   3;
        no.nx[nxind] = tmpcc-cc;
        if(str[nxind]<str[ind1]){
            // num =p[8-ind1];
            no.nx[ind1]  ;
        }
        if(str[nxind]<str[ind2]){
            //num =p[8-ind2];
            no.nx[ind2]  ;
        }
    }
    if(dir==3){
        //        num = num-p[8-xind]*no.nx[xind]  - p[8-nxind]*no.nx[nxind]   p[8-xind]*(no.nx[nxind] 2)    p[8-nxind]*(no.nx[xind]-cc);
        int ind1,ind2;
        ind1 = xind-1;
        ind2 = xind-2;
        int cc = 0;
        if(str[nxind]>str[ind1])cc  ;
        if(str[nxind]>str[ind2])cc  ;
        tmpcc = no.nx[xind];
        no.nx[xind]=no.nx[nxind] - 3;
        no.nx[nxind] = tmpcc cc;
        if(str[nxind]<str[ind1]){
            //num-=p[8-ind1];
            no.nx[ind1]--;
        }
        if(str[nxind]<str[ind2]){
            //num=p[8-ind2];
            no.nx[ind2]--;
        }
    }
    //    return num;
}
void solve(){
    //int front,rear;
    //    if(getnx()&1)
    //        return false;
    int num = getnumber();
    int hashnum;
    hashnum = charhash("123456789");
    node no("123456789",num,hashnum,nx);
    no.charstr();
    q.push(no);
    //vis[num] = true;
    int tmpnum,xind,nxind;
    int x,y,nx,ny;
    while(!q.empty()){
        no = q.front();
        q.pop();
        //  num = no.num;
        //if(goal==no.hashnum)return true;
        xind = no.xind;
        if(vis[no.hashnum])continue;
        vis[no.hashnum] = true;
        //xind = charstr(num);
        x = xind/3;
        y = xind%3;
        for(int i=0;i<4;  i){//右 左 下 上
            nx = x   dx[i];
            ny = y   dy[i];
            if(nx>=0&&nx<3&&ny>=0&&ny<3){
                nxind = nx*3 ny;
                tmpnum = gethash(no.str,no.hashnum,i,xind,nxind,no);
                int cc = no.str[nxind] - '0';
                no.str[xind] = no.str[nxind];
                no.str[nxind] = '9';
                // int chc = charhash(no.str);
                int t1,t2;
                //  t1 = no.num;
                t2 = no.hashnum;
                if(!vis[tmpnum]){
                    pa[tmpnum] = no.hashnum;
                    path[tmpnum] = i;
                    //   int tmpcc = num    (9 - cc)*(pw[nxind]-pw[xind]);
                    //  no.num = tmpcc;
                    no.hashnum = tmpnum;
                    no.xind = nxind;
                    q.push(no);
                }
                no.str[nxind] = no.str[xind];
                no.str[xind] = '9';
                // no.num = t1;
                no.hashnum = t2;
                no.xind = xind;
                restart(no.str,no.hashnum,i,xind,nxind,no);
            }
        }
    }
    //   return false;
}
int getdir(int num){
    switch(num){
        case 0: return 'l';
        case 1: return 'r';
        case 2: return 'u';
        case 3: return 'd';
    }
    return  0;
}
void output(bool flag,int hashnum){
    if(!flag){
        printf("unsolvable\n");
        return;
    }
    int cntans = 0;
    int tmp = hashnum;
    //char ss[]="ullddrurdllurdruldr";
    //printf("%d\n",strlen(ss));
    while(1){
        if(pa[tmp]==-1)break;
        ans[cntans  ] = path[tmp];
        tmp = pa[tmp];
        
    }
    //printf("%d",ans[0]);
    // printf("%d\n",cntans);
    for(int i=0;i<cntans;  i){
        putchar(getdir(ans[i]));
    }
    printf("\n");
}
void clear(){
    while(!q.empty()){
        q.pop();
    }
}
int main(){
    init();
    goal = 0;
    solve();
    //clear();
    bool flag;
    while(gets(nows)){
        flag = true;
        prepro();
        int hashnum = charhash(nows);
        if(!vis[hashnum])flag = false;
        output(flag,hashnum);
    }
    return 0;
}


最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复