[A*,启发式搜索] [SCOI2005] 骑士精神

链接：https://ac.nowcoder.com/acm/problem/20247
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：为了体现出骑士精神，他们必须以最少的步数完成任务。

输入描述:

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

输出描述:

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

示例1

输入

复制

输出

复制

7
-1

题意:

有一个5*5的棋盘，上面放了24个骑士棋子，和一个空位，每个棋子可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的空位
题目给了一个目标状态，问现在的状态转移到目标状态最少步数是多少，如果最少步数超过15则输出-1

思路:

模拟了第一个样例发现，棋盘中有7个与目标状态不同的骑士，而最少步数为7，也就是说最少步数最少为初始状态中有多少与标准不同的骑士的个数，这样刚好不会浪费格子，
所以枚举最少步数，从空格开始搜索，每次搜索预估代价，当前局面最小移动步数=现在有多少与标准不同的骑士的个数，
步数+预估代价>限制时(到14步时可能会有2个棋子不同但只要一步就能纠正这2个棋子,也就是步数+预估代价==16时是最大可接受范围,所以限制要设为大于等于16的数)或步数大于等于最小可行步数时返回，如果现在局面和标准相同则记录答案（只有步数小于最小可行步数时才会更新答案)，
如果搜索越界或现在的操作和上一个操作互逆（如果当前操作和上一个操作互逆却继续搜索那不就返回去了吗）则跳过，
否则交换搜索的棋子和当前棋子并搜索交换棋子的那个位置，且回溯时还原局面

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=10,inf=0x3f3f3f3f;
 4 int a[amn][amn],
 5 mp[amn][amn]={
 6     {1,1,1,1,1},
 7     {0,1,1,1,1},
 8     {0,0,2,1,1},
 9     {0,0,0,0,1},
10     {0,0,0,0,0}
11 },                          ///0^1=1,1^1=0,2^1=3,3^1=2,4^1=5,5^1=4...
12 dt[10][3]={                 ///方向储存时互逆操作相邻，这样就可以通过i^1，判断上一个操作是否和当前操作互逆
13     {-2,-1},{2,1},
14     {-1,-2},{1,2},
15     {1,-2},{-1,2},
16     {2,-1},{-2,1}
17 };
18 int ans,lim;
19 int hst(){          ///预估代价，最小移动步数=现在有多少与标准不同的骑士的个数
20     int h=0;
21     for(int i=0;i<5;i++)
22         for(int j=0;j<5;j++)
23             h+=(a[i][j]!=mp[i][j]);       ///判断现在有多少与标准不同的骑士
24     return h;
25 }
26 void dfs(int x,int y,int step,int last){
27     int h=hst();
28     if(step+h>lim||step>=ans)return;      ///步数+预估代价>限制时(到14步时可能会有2个棋子不同但只要一步就能纠正这2个棋子,也就是步数+预估代价==16时是最大可接受范围,所以限制要设为大于等于16的数)或步数大于等于最小可行步数时返回
29     if(h==0){           ///如果现在局面和标准相同则记录答案（只有步数小于最小可行步数时才会更新答案)
30         ans=step;
31         return ;
32     }
33     for(int i=0;i<8;i++){
34         int dx=x+dt[i][0],dy=y+dt[i][1];
35         if(dx<0||dx>4||dy<0||dy>4||(i^1)==last)continue;    ///如果搜索越界或现在的操作和上一个操作互逆（如果当前操作和上一个操作互逆却继续搜索那不就返回去了吗）则跳过
36             swap(a[dx][dy],a[x][y]);        ///交换
37             dfs(dx,dy,step+1,i);            
38             swap(a[dx][dy],a[x][y]);        ///回溯时还原局面
39     }
40 }
41 int main(){
42     int T,stx,sty;
43     char in;
44     scanf("%d",&T);
45     getchar();
46     while(T--){
47         for(int i=0;i<5;i++){
48             for(int j=0;j<5;j++){
49                 scanf("%c",&in);
50                 if(in=='1')
51                     a[i][j]=1;
52                 else if(in=='0')
53                     a[i][j]=0;
54                 else
55                     a[i][j]=2,stx=i,sty=j;
56             }
57             getchar();
58         }
59         ans=inf;
60         int h=hst();
61         for(int i=h;i<=16;i++){             ///枚举限制，最小限制从现在有多少与标准不同的骑士的个数开始，到一个大于等于16的数(太大了会超时),
到14步时可能会有2个棋子不同但只要一步就能纠正这2个棋子,也就是步数+预估代价==16时是最大可接受范围,所以限制要设为大于等于16的数
62             lim=i;
63             dfs(stx,sty,0,inf);
64         }
65         printf("%d
",ans>15?-1:ans);
66     }
67 }
68 /**
69 有一个5*5的棋盘，上面放了24个骑士棋子，和一个空位，每个棋子可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的空位
70 题目给了一个目标状态，问现在的状态转移到目标状态最少步数是多少，如果最少步数超过15则输出-1
71 模拟了第一个样例发现，棋盘中有7个与目标状态不同的骑士，而最少步数为7，也就是说最少步数最少为初始状态中有多少与标准不同的骑士的个数，这样刚好不会浪费格子，
72 所以枚举最少步数，从空格开始搜索，每次搜索预估代价，当前局面最小移动步数=现在有多少与标准不同的骑士的个数，
73 步数-1+预估代价>限制时(到14步时可能会有2个棋子不同但只要一步就能纠正这2个棋子,也就是步数+预估代价==16时是最大可接受范围,所以限制要设为大于等于16的数)或步数大于等于最小可行步数时返回，如果现在局面和标准相同则记录答案（只有步数小于最小可行步数时才会更新答案)，
74 如果搜索越界或现在的操作和上一个操作互逆（如果当前操作和上一个操作互逆却继续搜索那不就返回去了吗）则跳过，
75 否则交换搜索的棋子和当前棋子并搜索交换棋子的那个位置，且回溯时还原局面
76 **/