星星之火OIer：迭代加深（三）——骑士精神题目传送门基本思路代码实现后话

69 阅读 0 评论 46 点赞

我是靠谱客的博主有魅力草丛，最近开发中收集的这篇文章主要介绍星星之火OIer：迭代加深（三）——骑士精神题目传送门基本思路代码实现后话，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

迭代加深的前置知识请看这里辣

题目传送门

基本思路

代码实现

后话

题目传送门

题目大意：：一个 $5*5$ 的棋盘里有 $12$ 个黑马和 $12$ 个白马，还有一个空格，要求最少步数移动成这个样子：：

如果 $15$ 步内不能得到目标图形则输出 $-1$

基本思路

其实这道题不止可以用迭代加深做，也可以用双向 $BFS,A^*,IDA^*$ 都可以做

但既然我们现在在讲 $IDDFS$ ，我们还是用迭代加深来做吧

定义的深度用来表示到目前为止最大移动步数

然后还是要剪枝

然后就很简单了

然后就没有然后了

代码实现

#include<cmath>
#include<ctime>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define it int
#define ll long long
#define il inline
#define bl bool
#define db double
#define rt return
#define vd void
#define ch char
#define wi while
#define br break
#define gc getchar
#define pc putchar
#define ct continue//你什么都没看到
il vd read(it &x) {
    x=0;
    it f=1;
    ch s=gc();
    wi(s<'0'||s>'9') {
        if(s=='-')
            f=-1;
        s=gc();
    }
    wi(s>='0'&&s<='9') {
        x=x*10+s-48;
        s=gc();
    }
    x*=f;
}
il vd pr(it x) {
    if(x<0) {
        pc('-');
        x=-x;
    }
    if(x>9)
        pr(x/10);
    pc(x%10+48);
}//快读快输不解释
it mb[5][5]={{1,1,1,1,1},{0,1,1,1,1},{0,0,2,1,1},{0,0,0,0,1},{0,0,0,0,0}};//目标数组，空格为2
it a[5][5];//当前数组
it X[8]={1,1,-1,-1,2,2,-2,-2},Y[8]={2,-2,2,-2,1,-1,1,-1};//移动方向
bl flag;
il it check() {//剪枝
    it ans=0;//计算的是当前数组和答案数组不同的地方
    for(it i=0;i<5;i++)//最乐观估计
        for(it j=0;j<5;j++)//即最少要移动ans步
            if(a[i][j]!=mb[i][j])//不同
                ans++;
    rt ans;
}
it t,sx,sy;
il bl out(it x,it y) {//是否在图内
    if(x<0||x>4||y<0||y>4)
        rt 1;//出图了
    rt 0;//图内
}
vd iddfs(it x,it y,it s,it k) {//迭代加深搜索
    if(s==k) {
        if(check()==0)//完全匹配，得到答案
            flag=1;//已有答案
        rt;
    }
    for(it i=0;i<8;i++) {
        it nx=x+X[i];//移动
        it ny=y+Y[i];
        if(out(nx,ny))//是否出图
            ct;
        swap(a[x][y],a[nx][ny]);//移动之后，空位变道原来的位置
        if(s+check()<=k)//最乐观的情况下可以走
        	iddfs(nx,ny,s+1,k);//那就继续搜
        swap(a[x][y],a[nx][ny]);//回溯
    }
}
ch s;
it main() {
    read(t);
    while(t--) {
        for(it i=0;i<5;i++) {
            for(it j=0;j<5;j++) {
                s=gc();
                if(s=='*') {//特判一下
                    a[i][j]=2;
                    sx=i;//起点
                    sy=j;
                }
                else
                    a[i][j]=s-48;//化成数字
            }
            gc();
		}
        it k=0;
        for(;k<=15;k++) {//15步以内
            iddfs(sx,sy,0,k);//每个深度都要搜一下
            if(flag)
                br;
        }
        pr(k>15?-1:k),pc('n');//有没有答案
        flag=0;
    }
}