题解 UVA10181 【15-Puzzle Problem】

· · 题解

\texttt{Solution}

算法：\texttt{IDA*}

我们在暴力搜索的基础上，从小到大依次枚举每个目标深度进行搜索（迭代加深），并加上估价函数（启发式搜索），就可以将算法变成 \texttt{IDA*}，达到 \color{green}\texttt{Accept} 的目的。

此外，我们还需要加入的优化是：

优化 1：判定原来的十五数码是否有解。

优化 2：永远不走与上一步相反的路。

优化 3：当前步数 + 估价函数 > 目标深度，立即退出。

估价函数的值等同于当前状态下所有非 0 的数字到目标位置的曼哈顿距离之和。

代码（\color{green}\texttt{Accpet }\color{black}\texttt{410ms}，不是很快）：

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9'){
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9'){
        x=x*10+c-48;
        c=getchar();
    }
    return x*f;
}
struct pt{
    int val,cnt;
};
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
const char dc[4]={'R','L','D','U'};
const int px[16]={4,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4};
const int py[16]={4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3};
int f[5][5],way[100]; //f存放当前状态，way存放方案
int judge(){ //求出估价函数的值
    int sum=0;
    for (int i=1;i<=4;++i){
        for (int j=1;j<=4;++j){
            if (f[i][j]==0) continue;
            sum+=abs(i-px[f[i][j]])+abs(j-py[f[i][j]]);
        }
    }
    return sum;
}
int puz[16];,
bool solvable(){ //优化1，判断原15数码是否有解（这一段可以参照网络上的做法）
    int cnt=0,tot=0;
    for (int i=1;i<=4;++i){
        for (int j=1;j<=4;++j){
            puz[tot]=f[i][j];
            tot++;
        }
    }
    for (int i=0;i<16;++i){
        if (puz[i]==0)
            cnt+=3-i/4;
        else{
            for (int j=0;j<i;++j){
                if (puz[j] && puz[j]>puz[i]){
                    cnt++;
                }
            }
        }
    }
    return !(cnt&1);
}
int inv(int x){ //算出某个方向的反方向
    if (x==0) return 1;
    if (x==1) return 0;
    if (x==2) return 3;
    if (x==3) return 2;
}
bool flag,ans;
void swap(int &x,int &y){ //swap自己写可以稍微快一点
    int t=x;x=y;y=t;
}
void dfs(int x,int y,int t,int len,int last,int val){ //x,y表示0的位置，t表示当前步数，len表示目标步数，last表示上一步的方向，val表示当前的估价函数值
    if (flag) return; //找到解了立即退出
    if (val+t>len+1) return; //优化3
    if (t==len+1 && val==0){ //当前步数恰好等于目标步数+1，且估价函数等于0表示在目标步数下找到解了
        flag=true;
        for (int i=1;i<=len;++i){ //输出方案
            putchar(dc[way[i]]);
        }
        putchar('\n');
        return;
    }else if (t>len+1){ //当前步数大于目标步数+1，直接退出
        return;
    }
    pt b[5];
    int tot=0;
    for (int i=0;i<4;++i){ 
        if (i==inv(last)) continue; //优化2
        if (x+dx[i]<1 || x+dx[i]>4) continue; //越界了肯定不能要
        if (y+dy[i]<1 || y+dy[i]>4) continue;
        tot++; //加入一个可行移动
        swap(f[x][y],f[x+dx[i]][y+dy[i]]);
        b[tot].val=judge();
        b[tot].cnt=i;
        swap(f[x][y],f[x+dx[i]][y+dy[i]]);
    }
    if (tot==0) return; //没有可行移动也不用做了
    //sort(b+1,b+1+tot,cmp); //本来想按照估价函数排个序的，可是加了似乎会更慢 410ms->470ms
    for (int i=1;i<=tot;++i){ //对所有可行移动进行操作（其实可以和前面一段合并，似乎会更快些）
        swap(f[x][y],f[x+dx[b[i].cnt]][y+dy[b[i].cnt]]);
        way[t]=b[i].cnt;
        dfs(x+dx[b[i].cnt],y+dy[b[i].cnt],t+1,len,b[i].cnt,b[i].val); //进行移动
        swap(f[x][y],f[x+dx[b[i].cnt]][y+dy[b[i].cnt]]);
    }
}
int main(){
    int T=read();
    while (T --> 0){
        int x,y;
        for (int i=1;i<=4;++i){
            for (int j=1;j<=4;++j){
                f[i][j]=read();
                if (f[i][j]==0){
                    x=i;y=j; //找到0所在的位置
                }
            }
        } 
        if (judge()==0){ //如果原图本来就可以的话那么直接输出空行
            putchar('\n');
            continue;
        }
        if (!solvable()){ //优化1
            puts("This puzzle is not solvable.");
            continue;
        }
        flag=false;
        int startans=judge(),step=0;
        while (!flag){ 
            step++; //目标步数增加1，继续迭代
            dfs(x,y,1,step,-1,startans);
        }
    }
    return 0;
}