八数码II
↑ 题目链接
题目
在一个 \(3×3\) 的网格中，\(1∼8\) 这 8 个数字和一个 X 恰好不重不漏地分布在这 \(3×3\) 的网格中。
例如：
1 2 3
X 4 6
7 5 8
在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。
把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。
现在，给你一个初始网格状态，并希望你将其变换为一个目标网格状态，请你找到所需行动次数最少的方案。
我们用一行字符串来描述一种网格状态。
例如，网格：
1 2 3
X 4 6
7 5 8
用 123X46758 来表示。
输入格式
第一行包含整数 \(T\) ，表示共有 \(T\) 组测试数据。
每组数据占两行，第一行包含一个字符串表示初始网格状态，第二行包含一个字符串表示目标网格状态。
保证给定状态合法，并且一定有解。
输出格式
每组数据输出占两行，第一行输出 Case x: y，其中 x 为组别编号（从 1 开始），y为所需最少行动次数。
第二行输出具体行动方案，如果方案不唯一，则输出字典序最小的方案。
数据范围
\(1≤T≤200\)
输入样例：
2
12X453786
12345678X
564178X23
7568X4123
输出样例：
Case 1: 2
dd
Case 2: 8
urrulldr
思路
本题需要最小字典序，并且有多组样例。应该使用 \(IDA^{∗}\) 解题：
估值函数的选择：
- 每个点与目标点曼哈顿距离差的和。
在何时选择 \(A^{∗}\) 或 \(IDA^{∗}\) ：
- 需要最小字典序时，状态表示很大，指数增长较快时，使用 \(IDA^{∗}\)
- 若状态容易表示，指数增长较慢时，使用 \(A^{∗}\)（注意需要最小字典序时不能用 \(A^{∗}\) ，因为它不是按照顺序搜索的）
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
string s1,s2;
int pos[12];
int path[N];
string op="dlru";
int dx[]={1,0,0,-1};
int dy[]={0,-1,1,0};
//估值函数，当前状态和目标状态每个点的曼哈顿距离差的和
int f()
{
int res=0;
for(int i=0;i<9;i++)
{
if(s1[i]!='X')
{
int num=s1[i]-'0';
res+=abs(i/3-pos[num]/3)+abs(i%3-pos[num]%3);
}
}
return res;
}
bool dfs(int u,int depth)
{
//如果当前深度 + 估值深度 > 最大深度，直接回溯
if(f()+u>depth)return false;
//找到答案，返回true
if(s1==s2)return true;
//存X当前的位置序号
int k;
for(int i=0;i<9;i++)
if(s1[i]=='X')
{
k=i;
break;
}
int x=k/3,y=k%3;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=3||b<0||b>=3)continue;
//避免往回走(至少走了1步,且上一步和当前一步和为3)
//d+u=0+3=3 l+r=1+2=3
//下(d):0 左(l):1 右(r):2 上(u):3
if(u>0&&i+path[u-1]==3)continue;
swap(s1[k],s1[a*3+b]);
path[u]=i;//保存路径
if(dfs(u+1,depth))return true;//找到答案，一路返回true
swap(s1[k],s1[a*3+b]);
}
return false;
}
int main()
{
int T;
cin>>T;
for(int i=1;i<=T;i++)
{
cin>>s1>>s2;
for(int i=0;i<9;i++)
if(s2[i]!='X')
pos[s2[i]-'0']=i;
//迭代加深IDA*
int depth=0;
while(!dfs(0,depth))depth++;
printf("Case %d: %d\n",i,depth);
for(int i=0;i<depth;i++)
printf("%c",op[path[i]]);
puts("");
}
return 0;
}