此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。

题目链接：

https://www.luogu.org/problemnew/show/P2324

 

题目描述

 

 

输入输出格式

输入格式：

第一行有一个正整数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

说明

分析：

这道题用到了迭代加深搜索

或者准确的说是IDA*

但如果这道题用迭代加深+常数优化的话

会跑的更快一些（好吧是因为我不会IDA*

很显然，如果枚举骑士分布，状态巨多，且不好判断空格在哪，所以换个思路，不移骑士，移空格

迭代加深就是每次限制搜索深度，十分广搜

但是，仔细想想，只有四种情况：

1.原来骑士归位了，改完没归位

2.原来骑士没归位，改完归位了

3.原来空位没归位，改完归位了

4.原来空位归位了，改完没归位

参考代码：

 

1 #include 
     
       2 #include 
      
        3 #define f(i, a, b) for (i = a; i <= b; ++i) 4 using namespace std; 5 int a[6][6]; 6 int b[6][6] = {
    {}, 7               {
   0, 1, 1, 1, 1, 1}, 8               {
   0, 0, 1, 1, 1, 1}, 9               {
   0, 0, 0, -1, 1, 1},10               {
   0, 0, 0, 0, 0, 1},11               {
   0, 0, 0, 0, 0, 0}};12 int dx[8] = {-2, -2, -1, 1, -1, 1, 2, 2};13 int dy[8] = {-1, 1, 2, 2, -2, -2, -1, 1};14 int mxd;15 inline int read(){16     char ch, c;17     int res = 0;18     while (ch  = getchar(), ch < '0' || ch > '9') c = ch;19     res = ch - 48;20     while (ch = getchar(), ch >= '0' && ch <= '9')21     res = (res << 3) + (res << 1) + ch - 48;22     if (c == '-') res = -res;23     return res;  24 }25 int check(int k, int x, int y, int sum, int la){26     if (k + sum > mxd) return 0;27     if (sum == 0) return 1;28     int i, xx, yy, p;29     bool fl = 0, fll = 0;30     f(i, 0, 7){31         if (i != (7 - la)){32             xx = x + dx[i];33             yy = y + dy[i];34             p = sum;35             if (xx <= 5 && xx > 0 && yy <= 5 && yy > 0){36                 if (a[xx][yy] == b[xx][yy] && a[xx][yy] != b[x][y]) ++p;37                 if (a[xx][yy] != b[xx][yy] && a[xx][yy] == b[x][y]) --p;38                 if (b[xx][yy] == -1) --p;39                 if (b[x][y] == -1) ++p;40                 a[xx][yy] ^= a[x][y], a[x][y] ^= a[xx][yy], a[xx][yy] ^= a[x][y];41                 fl = check(k + 1, xx, yy, p, i);42                 if (fl) return 1;43                 a[xx][yy] ^= a[x][y], a[x][y] ^= a[xx][yy], a[xx][yy] ^= a[x][y];44             }45         }46     }47     return 0;48 }49 int main(){50     int i, j, t;51     char k;52     scanf("%d", &t);53     while (t){54         int mn = 0, x, y;55         f(i, 1, 5)56         f(j, 1, 5){57             cin >> k;58             if (k == '*'){59                 a[i][j] = -1;60                 x = i, y = j;61             }62             else a[i][j] = k - '0';63             if (a[i][j] != b[i][j]) mn++;64         }65         bool fl = 0;66         f(i, mn, 16){67             mxd = i;68             if (check (0, x, y, mn, -1)){69                 printf("%d\n", i - 1), fl = 1; break;70             }71         }72         if (!fl)73         printf("-1\n");74         t--;75     }76     return 0;77 }