题解 P2324 【[SCOI2005]骑士精神】

niiick · 2018-06-28 18:16:51 · 题解

迭代加深的A*算法

所谓迭代加深就是每次限制搜索深度， 这样可以在整个搜索树深度很大而答案深度又很小的情况下大大提高效率

因为最大步数不超过15， 所以直接枚举1到15作为最大步数进行迭代加深搜索判断

在这里我们的*A估价函数**设置为

当前状态还有多少个位置与目标状态不对应

若当前步数+估价函数值>枚举的最大步数 则直接返回

当然这只是基本思路，搜索还可以有很大优化

我们在搜索中再加入最优性剪枝， 显然当前枚举下一个状态时如果回到上一个状态肯定不是最优， 所以我们在枚举下一状态时加入对这种情况的判断

将状态数组对称排列会很方便进行这一操作

int nxtx[]={1,1,2,2,-2,-2,-1,-1};
int nxty[]={2,-2,1,-1,1,-1,2,-2};

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

int n;
int ans[6][6]=
{{0,0,0,0,0,0},
 {0,1,1,1,1,1},
 {0,0,1,1,1,1},
 {0,0,0,2,1,1},
 {0,0,0,0,0,1},
 {0,0,0,0,0,0}};
int nxtx[]={1,1,2,2,-2,-2,-1,-1};
int nxty[]={2,-2,1,-1,1,-1,2,-2};
int a[10][10],k;
int judge;

int check()
{
    for(int i=1;i<=5;++i)
    for(int j=1;j<=5;++j)
    if(ans[i][j]!=a[i][j])return 0;
    return 1;
}

int test(int step)
{
    int cnt=0;
    for(int i=1;i<=5;++i)
    for(int j=1;j<=5;++j)
    if(ans[i][j]!=a[i][j]){ if(++cnt+step>k) return 0;}
    return 1;
}

void A_star(int step,int x,int y,int pre)//pre记录上一步怎么到当前状态
{
    if(step==k){ if(check())judge=1; return;}
    if(judge) return;
    for(int i=0;i<8;++i)
    {
        int nx=x+nxtx[i],ny=y+nxty[i];
        if(nx<1||nx>5||ny<1||ny>5||i+pre==7) continue;//加入了上述的最优性剪枝
        swap(a[x][y],a[nx][ny]);
        if(test(step)&&!judge) A_star(step+1,nx,ny,i);//A*估价再向下搜索
        swap(a[x][y],a[nx][ny]);
    }
}

int main()
{
    n=read();
    while(n--)
    {
        int x,y; judge=0;
        for(int i=1;i<=5;++i)
        {
            char ss[7]; scanf("%s",&ss);
            for(int j=0;j<5;++j)
            if(ss[j]=='*') a[i][j+1]=2,x=i,y=j+1;
            else a[i][j+1]=ss[j]-'0';
        }
        for(k=1;k<=15;++k)
        {
            A_star(0,x,y,-1);
            if(judge) { printf("%d\n",k); break;}
        }
        if(!judge)printf("-1\n");
    }
    return 0;
}
//niiick