$$\color{Purple}{kuangbin题解目录}$$
描述
在一个 $3×3$ 的网格中,$1 \\sim 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 \\le T \\le 200$
输入样例:
2
12X453786
12345678X
564178X23
7568X4123
输出样例:
Case 1: 2
dd
Case 2: 8
urrulldr
思路
- 可参考算法提高课 Acwing180.排书该题的
IDA*
.- 利用
IDA*算法
解决该题.- 从一个状态$a$走到另一个状态$b$,定义$d_i$为$a$中$i$的位置与$b$中$i$的位置的曼哈顿距离,至少需要$\sum_{i=1}^{8} d_i$步,故可作为其估价函数.
- 在迭代加深的过程中,若当前的估价函数+已走的步数大于当前最大深度时,返回$0$,若当前状态$a$与状态$b$相同时,则可以到达该点,则返回$1$,注意剪枝(避免往回走,即不要先走了一步,然后又走回来),若$4$个方向都无解,返回$0$.
- 注意该题的要求是字典序最小,应采用$下(d) \rightarrow 左(l) \rightarrow 右(r) \rightarrow 上(u)$的顺序遍历,这样保证结果一定是字典序最小的.
代码
// Problem: 八数码II
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4231/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-12 14:07:30
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1010
using namespace std;
typedef long long ll;
int t;
string s1,s2;//s1存起始字符串,s2存最终字符串
int pos[10];//存最终状态的位置
//字典序最小dlru
char op[4]={'d','l','r','u'};//下左右上
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};//方向与操作同步
int path[MAXN];
int f()//估价函数
{
int res=0;
for(int i=0;i<=8;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;
}
int dfs(int root,int depth)
{
if(f()+root>depth)//估价函数+当前走的步数大于当前最大深度,返回0
return 0;
if(s1==s2)//表示起点走到了终点,返回1
return 1;
int temppos=0;//存X的当前位置序号
for(int i=0;i<=8;i++)
if(s1[i]=='X')
temppos=i;
//将序号坐标化
int pos_x=temppos/3,pos_y=temppos%3;
for(int i=0;i<=3;i++)
{
int dx=pos_x+dir[i][0],dy=pos_y+dir[i][1];
//避免往回走(至少走了1步,且上一步和当前一步和为3)
//d+u=0+3=3 l+r=1+2=3
//下(d):0 左(l):1 右(r):2 上(u):3
if(root>0&&i+path[root-1]==3)
continue;
//避免越界
if(dx<0||dx>=3||dy<0||dy>=3)
continue;
//交换
swap(s1[temppos],s1[dx*3+dy]);
path[root]=i;
if(dfs(root+1,depth)==1)
return 1;
swap(s1[temppos],s1[dx*3+dy]);//恢复现场
}
return false;//4个方向都不行,返回0
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> t;
int Case=1;
while(t--)
{
cin >> s1 >> s2;
for(int i=0;i<=8;i++)
if(s2[i]!='X')
pos[s2[i]-'0']=i;
//迭代加深IDA*
int depth=0;
while(dfs(0,depth)==0)
depth++;
printf("Case %d: %d\n",Case++,depth);
for(int i=0;i<depth;i++)
cout << op[path[i]];
cout << endl;
}
return 0;
}