[IDA*] 洛谷 P2324 骑士精神

川长思鸟来 2021-10-01 03:32 283阅读 0赞

## 题目描述 ##

![1389.png][]

## 输入输出格式 ##

输入格式：

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，\*表示空位。两组数据之间没有空行。

输出格式：

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

## 输入输出样例 ##

输入样例\#1：  复制

2
    10110
    01*11
    10111
    01001
    00000
    01011
    110*1
    01110
    01010
    00100

输出样例\#1：  复制

7
    -1

## 说明 ##

![1390.png][]

# 题解 #

*  其实就是迭代加深的A\*就是IDA\*
 *  当前状态还有多少个位置与目标状态不对应
    
     
 *  若当前步数+估价函数值>枚举的最大步数 则直接返回

# 代码 #

1 #include <cstdio>
     2 #include <iostream>
     3 using namespace std;
     4 const int map[5][5]={
        { 1, 1, 1, 1, 1},
     5                      { 0, 1, 1, 1, 1},
     6                      { 0, 0,-1, 1, 1},
     7                      { 0, 0, 0, 0, 1},
     8                      { 0, 0, 0, 0, 0}};
     9 const int fx[8]={
        1, 1,-1,-1,2, 2,-2,-2};
    10 const int fy[8]={
        2,-2, 2,-2,1,-1, 1,-1};
    11 struct edge{
        int x,y,p;}u,k;
    12 int n,m,ans,T,a[10][10];
    13 char s[10];
    14 edge pd()
    15 {
    16     u.p=0;
    17     for(int i=1;i<=5;i++)
    18         for(int j=1;j<=5;j++)
    19         {
    20             if(a[i][j]==-1) u.x=i,u.y=j;
    21             u.p+=a[i][j]!=map[i-1][j-1];
    22         }
    23     return u;
    24 }
    25 bool dfs(int x)
    26 {
    27     edge k=pd();
    28     if (!k.p) return true;
    29     if (x+k.p-1>ans) return false;
    30     for (int i=0;i<=7;i++)
    31     {
    32         int xx=k.x+fx[i],yy=k.y+fy[i];
    33         if (xx<1||xx>5||yy<1||yy>5) continue;
    34         swap(a[k.x][k.y],a[xx][yy]);
    35         if (dfs(x+1)) return true;
    36         swap(a[k.x][k.y],a[xx][yy]);
    37     }
    38     return false;
    39 }
    40 int main()
    41 {
    42     scanf("%d",&T);
    43     while (T--)
    44     {
    45         for (int i=1;i<=5;i++)
    46         {
    47             scanf("%s",s+1);
    48             for (int j=1;j<=5;j++) a[i][j]=s[j]=='*'?-1:s[j]-48;
    49         }
    50         for (ans=1;ans<=15;ans++) if(dfs(0)) break;
    51         printf("%d\n",ans<=15?ans:-1);
    52     }
    53 }

转载于:https://www.cnblogs.com/Comfortable/p/10433606.html

[1389.png]: /images/20210724/67f8ce517f534f01943ac4c3648ce629.png
[1390.png]: /images/20210724/dc15451b5c654377aa00e762665c4b35.png