模型
答案求最小步数
在某步数内一定可以完成 或 超出某步数认为无解
随便写点注意事项
注意估值函数的选取
一般为 当前状态到最终状态的最短步数+已走的步数 是否大于 枚举的深度
- 在[ $flood \ it$ ] 中：定义了专门的求估值函数（好像就变成IDA*了
$\text{dfs}(now+1)$ 失败后及时回复现场
$eg$ : [ $八数码难题$ ] 中：通过两数交换
1
2
3
4
5swap(sta[nx][ny],sta[x][y]);
if(test(step)) A(step+1,nx,ny,i);
swap(sta[nx][ny],sta[x][y]);$eg$ : [ $骑士精神$ ] 中：毫无可读性的两数交换
1
2
3
4
5
6
7a[x][y]^=a[xx][yy],a[xx][yy]^=a[x][y],a[x][y]^=a[xx][yy];//什么是swap
bool flag=dfs(step+1,maxstep,tmp,xx,yy,i);
if(flag) return 1;
a[x][y]^=a[xx][yy],a[xx][yy]^=a[x][y],a[x][y]^=a[xx][yy];//回复现场$eg$ : [ $flood \ it$ ] 中：通过对数组的交换
1
2
3
4
5memcpy(tmp,vis,sizeof vis);
if(fill(i) && dfs(now+1)) return 1;
memcpy(vis,tmp,sizeof vis);//还原
在枚举每次状态改变时，注意及时的剪枝，即使是看起来并不重要的
栗子 $1$：出界
好容易忘qwq（写总结的时候也忘了
栗子 $2$：当前移动恰与上一步相反
剪枝方法：
仔细选取 $dx[ \ ],dy[ \ ]$
判断两次移动的方向和 $i+pre$
$eg$ : [ $骑士精神$ ] 中：
1
2
3
4
5const int dx[8]={-1,1,2,2,-2,-2,-1,1};
const int dy[8]={2,2,1,-1,1,-1,-2,-2};
//如此保证两个相反的方向加和为7
栗子 $3$：当前步恰好完成,或通过估价函数得到当前步可行
$eg$ : [$Power \ Calculus$] 中：
1
if(now==n || now<<(MAX-step)==n/*题目背景可推断*/) return 1;
$eg$ : [$flood \ it$] 中：
1
2
3rei g=get_val();
···
if(!g) return 1;
栗子 $4$：针对当前块的扩展问题，要得到周围与之相邻的块的编号（我不知道我在写什么
剪枝方法：
开 $vis[ \ ]$ 数组并及时维护
$eg$ : [ $flood \ it$ ] 中：
自行读代码
栗子 $5$：考虑答案的单调性
$eg$ : [$Addition \ Chains$] 中：
1
2
3
4
5
6
7
8for(rei i=0;i<now;++i)
for(rei j=i;j<now;++j){//从i开始啊qwq
rei tmp=ans[i]+ans[j];
if(tmp>n) break;//ans单增
if(tmp<=ans[now-1]) continue;
ans[now]=tmp;
if(dfs(now+1,MAX)) return 1;
}
注意一下开始 $\text{dfs}$ 的深度为 $0/1$
关系到答案输出是 $MAX$ 还是 $MAX-1$