八数码

hdu1043 Eight

题意

给定一个\(3*3\)的棋盘，含有数字\([1,8]\)以及一个字母\(x\)表示空格，每一步可以将空格和上下左右四个相邻位置的数字交换，判断是否可以将棋盘变成图中所示的目标棋盘，如果可以，给出一种移动空格的方案。

题解

如果初始棋盘和目标棋盘按行展开之后的序列的逆序对奇偶性一致，则可以转换，否则无法转换
可以使用IDA*进行搜索，估价函数使用曼哈顿距离
ps. 由于使用了估价函数，答案不一定在第deep层被搜索到

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL,LL>
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
using namespace std;

int a[5][5],b[15],d[400010],deep;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char dir[4]={'u','d','l','r'};
bool f;
map<int,bool> vis;

bool judge(){
    int cnt=0;
    for(int i=0;i<9;i++){
        for(int j=i+1;j<9;j++){
            if(b[j] && b[j]<b[i]){
                cnt^=1;
            }
        }
    }
    return cnt==0;
}

int ToInt(){
    int res=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            res=res*10+a[i][j];
        }
    }
    return res;
}

int Astar(){
    int h=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(a[i][j]){
                int nx=(a[i][j]-1)/3;
                int ny=(a[i][j]-1)%3;
                h+=abs(i-nx)+abs(j-ny);
            }
        }
    }
    return h;
}

void IDAstar(int x,int y,int step){
    if(f) return;
    int h=Astar();
    int cur=ToInt();
    if(cur==123456780){
        for(int i=0;i<step;i++) cout<<dir[d[i]];
        cout<<"\n";
        f=true;
        return;
    }
    //IDA*剪枝，现实+理想>现状，则返回
    if(step+h>deep) return;
    if(vis[cur]) return;
    vis[cur]=true;
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx>=0 && tx<3 && ty>=0 && ty<3){
            d[step]=i;
            swap(a[x][y],a[tx][ty]);
            IDAstar(tx,ty,step+1);
            swap(a[x][y],a[tx][ty]);
        }
    }
}

int main(){
    char ch;
    int sx,sy;
    while(cin>>ch){
        int cnt=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(i==0 && j==0){}
                else{
                    cin>>ch;
                }
                if(ch=='x'){
                    a[i][j]=0;
                    sx=i;
                    sy=j;
                }
                else{
                    a[i][j]=ch-'0';
                }
                b[cnt++]=a[i][j];
            }
        }
        if(!judge()){
            printf("unsolvable\n");
            continue;
        }
        f=false;
        deep=-1;
        while(!f){
            vis.clear();
            deep++;
            IDAstar(sx,sy,0);
        }
    }
}

参考博客

hdu3567 Eight II

题意

给定八数码的初始棋盘和目标棋盘，保证一定可以转换，给出步数最少的方案中字典序最小的方案。

题解

在上一题的基础上稍作修改：
1.每一步空格移动的搜索顺序应该按照字典序最小的方案"dlru"进行
2.由于IDA*本质是dfs，所以计算最短步数时不能对第一次搜索到的状态判重
3.不进行将空格左移和右移连续或者上移和下移连续的操作

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL,LL>
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
using namespace std;

int T,cas,a[5][5],b[15],d[400010],deep,target,pos[15];
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
char dir[4]={'d','l','r','u'},str1[15],str2[15];
bool f;

int ToInt(){
    int res=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            res=res*10+a[i][j];
        }
    }
    return res;
}

int Astar(){
    int h=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(a[i][j]){
                int nx=pos[a[i][j]]/3;
                int ny=pos[a[i][j]]%3;
                h+=abs(i-nx)+abs(j-ny);
            }
        }
    }
    return h;
}

void IDAstar(int x,int y,int pre,int step){
    if(f) return;
    int h=Astar();
    int cur=ToInt();
    if(cur==target){
        printf("Case %d: %d\n",cas,step);
        for(int i=0;i<step;i++) cout<<dir[d[i]];
        cout<<"\n";
        f=true;
        return;
    }
    //IDA*剪枝，现实+理想>现状，则返回
    if(step+h>deep) return;
    for(int i=0;i<4;i++){
        if(i+pre==3) continue;
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx>=0 && tx<3 && ty>=0 && ty<3){
            d[step]=i;
            swap(a[x][y],a[tx][ty]);
            IDAstar(tx,ty,i,step+1);
            swap(a[x][y],a[tx][ty]);
        }
    }
}

int main(){
    scanf("%d",&T);
    while(T--){
        ++cas;
        scanf("%s %s",str1,str2);
        char ch;
        int sx,sy;
        int cnt=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                ch=str1[i*3+j];
                if(ch=='X'){
                    a[i][j]=0;
                    sx=i;
                    sy=j;
                }
                else{
                    a[i][j]=ch-'0';
                }
                b[cnt++]=a[i][j];
            }
        }
        target=0;
        for(int i=0;i<9;i++){
            ch=str2[i];
            if(ch=='X'){
                target*=10;
                pos[0]=i;
            }
            else{
                target=target*10+ch-'0';
                pos[ch-'0']=i;
            }
        }
                f=false;
                deep=-1;
                while(!f){
                    deep++;
                    IDAstar(sx,sy,-1,0);
                }
        }
}