洛谷P2324/SCOI2005 骑士精神

@Pelom  November 7, 2019

题意

给出一个初始棋盘,要求移动成目标棋盘,询问是否能在$15$步内做到;若能,输出最少步数;否则输出$-1$

数据范围: 棋盘为$5 \times 5$

题解

移动马则考虑的情况过于复杂,因此选择移动空位
迭代加深搜索:逐步加大搜索的步数;但对于$-1$情况仍然需要搜完
增加估价函数,计算有多少个位置不同(即所需的可能最小步数)

inline int eva(){
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            res+=a[i][j]!=goal[i][j];
    return res-1;
}

其中结果$-1$是因为空位对结果没有影响(若所有马都在自己的位置上,那么空位也一定在自己的位置上)
若估价$+$已走步数$>$最大深度,则返回(此情况下不可能有解)

优化:

  • 若有解直接返回
  • 不走回头路(记录上次位置)

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int n=5;
const int d=15;
int t,sx,sy;
char s[n+1];
int a[n+1][n+1];
bool f;
int v[8][2]={
    {1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}
};
int goal[n+1][n+1]={
    {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}
};
inline int eva(){
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            res+=a[i][j]!=goal[i][j];
    return res-1;
}
void dfs(int x,int y,int px,int py,int s,int d){
    if(f)
        return ;
    int h=eva();
    if(s+h>d)
        return ;
    if(h==-1){
        f=1;
        return ;
    }
    for(int i=0;i<8;i++){
        int nx=x+v[i][0],ny=y+v[i][1];
        if(nx<1 || nx>n || ny<1 || ny>n || (nx==px && ny==py))
            continue;
        swap(a[x][y],a[nx][ny]);
        dfs(nx,ny,x,y,s+1,d);
        swap(a[x][y],a[nx][ny]);
    }
}
int main(){
    scanf("%d",&t);
    for(;t--;){
        f=0;
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);
            for(int j=1;j<=n;j++){
                if(s[j]=='*'){
                    sx=i,sy=j;
                    a[i][j]=2;
                }
                else a[i][j]=s[j]-'0';
            }
        }
        for(int i=1;i<=d;i++){
            dfs(sx,sy,0,0,0,i);
            if(f){
                printf("%d\n",i);
                break;
            }
        }
        if(!f)
            puts("-1");
    }
    return 0;
}

添加新评论