启发式搜索只能深搜
一般也是用来解决最优解问题的
在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士&＃xff0c; 且有一个空位。
在任何时候一个骑士都能按照骑士的走法&＃xff08;它可以走到和它横坐标相差为1&＃xff0c;纵坐标相差为2或者横坐标相差为2&＃xff0c;纵坐标相差为1的格子&＃xff09;移动到空位上。
给定一个初始的棋盘&＃xff0c;怎样才能经过移动变成如下目标棋盘&＃xff1a; 为了体现出骑士精神&＃xff0c;他们必须以最少的步数完成任务。
引入了启发函数之后&＃xff0c;可以很好地改善效率&＃xff0c;但是只能深搜
1 #include
2 #include
3 #include
4 using namespace std;
5 int T,k;
6 int ans[5][5]&＃61;{{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 int xx[8]&＃61;{1,1,-1,-1,2,2,-2,-2};
12 int yy[8]&＃61;{2,-2,2,-2,1,-1,1,-1};
13 int flag&＃61;0;
14 int judge(int a[5][5])
15 {
16 for(int i&＃61;0;i<5;i&＃43;&＃43;)
17 for(int j&＃61;0;j<5;j&＃43;&＃43;)
18 if(ans[i][j]!&＃61;a[i][j])return 0;
19 return 1;
20 }
21 int eva(int a[5][5],int s)
22 {
23 int v&＃61;0;
24 for(int i&＃61;0;i<5;i&＃43;&＃43;)
25 for(int j&＃61;0;j<5;j&＃43;&＃43;)
26 if(a[i][j]!&＃61;ans[i][j]){v&＃43;&＃43;;if(v&＃43;s>k)return 0;}
27 return 1;
28 }
29 void search(int s,int a[5][5],int x,int y)
30 {
31 if(s&＃61;&＃61;k){if(judge(a))flag&＃61;1;return;}
32 if(flag&＃61;&＃61;1)return;
33 for(int i&＃61;0;i<8;i&＃43;&＃43;)
34 {
35 int nowx&＃61;x&＃43;xx[i],nowy&＃61;y&＃43;yy[i];
36 if(nowx<0||nowx>4||nowy<0||nowy>4)continue;
37 swap(a[x][y],a[nowx][nowy]);
38 if(eva(a,s))search(s&＃43;1,a,nowx,nowy);
39 swap(a[x][y],a[nowx][nowy]);
40 }
41 }
42 int main()
43 {
44 scanf("%d",&T);
45 while(T--)
46 {
47 int a[5][5];int x,y;
48 memset(a,0,sizeof(a));
49 for(int i&＃61;0;i<5;i&＃43;&＃43;)
50 {
51 char ch[10];scanf("%s",ch);
52 for(int j&＃61;0;j<5;j&＃43;&＃43;)
53 {
54 if(ch[j]&＃61;&＃61;&＃39;*&＃39;){a[i][j]&＃61;2;x&＃61;i;y&＃61;j;}
55 else a[i][j]&＃61;ch[j]-&＃39;0&＃39;;
56 }
57 }
58 for(k&＃61;1;k<&＃61;15;k&＃43;&＃43;)
59 {search(0,a,x,y);if(flag){printf("%d\n",k);break;}}
60 if(!flag)printf("-1\n");
61 else flag&＃61;0;
62 }
63 return 0;
64 }
京公网安备 11010802041100号