北京门户网站,青海西宁做网站多少钱,实训建设网站的目的,烟台做网站多少钱迭代加深搜索。 剪枝#xff1a;当满足以下任意一个条件退出#xff1a; 1.当前已搜到答案时#xff08;ans!-1||sum0#xff09; 2.剩余步数1当前局面与目标局面不同的格子数sum 时#xff08;因为n步最多改变n1个格子#xff09; 3.当前步数当前规定最大步数时… 迭代加深搜索。 剪枝当满足以下任意一个条件退出 1.当前已搜到答案时ans!-1||sum0 2.剩余步数1当前局面与目标局面不同的格子数sum 时因为n步最多改变n1个格子 3.当前步数当前规定最大步数时 1 #includecstdio2 #includecstring3 using namespace std;4 const int n5,m8,maxstep15;5 int a[6][6],b[6][6]{{0,0,0,0,0,0},6 {0,1,1,1,1,1},{0,0,1,1,1,1},7 {0,0,0,-1,1,1},{0,0,0,0,0,1},8 {0,0,0,0,0,0}};9 int fh[9]{0,-2,-1,1,2,2,1,-1,-2},
10 fl[9]{0,1,2,2,1,-1,-2,-2,-1};
11 int ex,ey,ans,step;
12 void swap(int,int,int,int),work(),
13 dfs(int,int,int),read();
14 int change(char),check(),pd(int,int);
15 int main(){
16 int t;
17 scanf(%d,t);
18 for (int i1;it;i) work();
19 return 0;
20 }
21 void work(){
22 ans-1;read();
23 for (step0;stepmaxstep;step){
24 dfs(0,ex,ey);
25 if (ans!-1) break;
26 }
27 printf(%d\n,ans);
28 return;
29 }
30 void read(){
31 char c[7];
32 for (int i1;in;i){
33 scanf(%s,c);
34 for (int j0;jn;j){
35 a[i][j1]change(c[j]);
36 if (a[i][j1]-1){
37 exi;eyj1;
38 }
39 }
40 }
41 return;
42 }
43 void dfs(int deep,int p,int q){
44 int x,y,sum;
45 if (ans!-1) return;
46 sumcheck();
47 if (deepstep){
48 if (!sum) ansdeep;return;
49 }
50 else if (step-deep1sum) return;
51 if (deepstep) return;
52 for (int i1;im;i){
53 xpfh[i];yqfl[i];
54 if (pd(x,y)){
55 swap(x,y,p,q);
56 dfs(deep1,x,y);
57 swap(x,y,p,q);
58 }
59 }
60 }
61 int change(char c){
62 if (c1) return 1;
63 if (c0) return 0;
64 if (c*) return -1;
65 }
66 int check(){
67 int sum0;
68 for (int i1;in;i)
69 for (int j1;jn;j)
70 if (a[i][j]!b[i][j]) sum;
71 return sum;
72 }
73 int pd(int p,int q){
74 if (p1q1pnqn) return 1;
75 return 0;
76 }
77 void swap(int x,int y,int p,int q){
78 int tmp;
79 tmpa[x][y];a[x][y]a[p][q];a[p][q]tmp;
80 return;
81 } STD 转载于:https://www.cnblogs.com/Absolute-Zero/p/5833960.html
