则输出步数,保险最少存在二个恐怕的分数表

bt365体育在线 1Input第壹行包罗八个正整数n,队容的个数。第壹行包含n个非负整数,即每支阵容的得分。Output输出仅一行,即恐怕的分数表数目。保险最少存在1个只怕的分数表。Sample
Input

Description

在二个5×5的棋盘上有拾2个反革命的轻骑和十三个冰雪蓝的铁骑,
且有2个空位。在其余时候3个铁骑都能依据骑士的走法(它可以走到和它横坐标相差为1,纵坐标相差为2依旧横坐标相差为2,纵坐标相差为1的格子)移动到空位上。
给定两个上马的棋盘,怎么样才能经过移动成为如下目的棋盘:
为了显示出骑士精神,他们不可以不以最少的步数落成职分。

bt365体育在线 2

6
5 6 7 7 8 8

Input

首先行有贰个正整数T(T<=10),表示一共有N组数据。接下来有T个5×5的矩阵,0意味藏黄绿骑士,1表示紫铜色骑士,*代表空位。两组数据里面一直不空行。

Sample Output

Output

对此每组数据都输出一行。尽管能在15步以内(包蕴15步)到达目的状态,则输出步数,否则输出-1。

121

Sample Input

2
10110
01*11
10111
01001
bt365体育在线,00000
01011
110*1
01110
01010
00100

Hint

Sample Output

7
-1

 

正解:迭代强化搜索+启发式搜索(A*搜索)。

实在作者觉着那题的剪枝就是无独有偶的倾向剪枝而已。。

直接爆搜肯定T飞,我们考虑怎么剪枝。首先,这题用广搜会爆,所以我们用迭代深化搜索。假使当前步数+还需走的步数>需要步数,就足以剪枝了。前边那多少个可以透过相比较当前棋盘与对象棋盘有多少个棋子来鲜明。然后大家就能学有所成AC此题。。

 

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define inf (1<<30)
14 #define il inline
15 #define RG register
16 #define ll long long
17 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
18 
19 using namespace std;
20 
21 const int d1[9]={0,1,2,1,2,-2,-1,-2,-1},d2[9]={0,2,1,-2,-1,1,2,-1,-2};
22 int a[7][7],goal[7][7],stx,sty,d,flag;
23 char x;
24 
25 il int gi(){
26     RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
27     if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
28 }
29 
30 il char gc(){ RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='*') ch=getchar(); return ch; }
31 
32 il int check(int a[7][7]){
33     for (RG int i=1;i<=5;++i)
34     for (RG int j=1;j<=5;++j)
35         if (a[i][j]!=goal[i][j]) return 0;
36     return 1;
37 }
38 
39 il int go(int a[7][7],RG int had){
40     RG int res=0;
41     for (RG int i=1;i<=5;++i)
42     for (RG int j=1;j<=5;++j)
43         if (a[i][j]!=goal[i][j]) res++;
44     return had+res<=d;
45 }
46 
47 il void dfs(int a[7][7],RG int x,RG int y,RG int dep,RG int last){
48     if (check(a)){ flag=1; return; }
49     if (dep==d) return; RG int s[7][7],x1,y1;
50     for (RG int i=1;i<=5;++i)
51     for (RG int j=1;j<=5;++j) s[i][j]=a[i][j];
52     for (RG int i=1;i<=8;++i){
53     if (last+i==9) continue;
54     x1=x+d1[i],y1=y+d2[i];
55     if (x1<=0 || x1>5) continue;
56     if (y1<=0 || y1>5) continue;
57     swap(s[x][y],s[x1][y1]);
58     if (go(s,dep)){
59         dfs(s,x1,y1,dep+1,i);
60         if (flag) return;
61     }
62     swap(s[x][y],s[x1][y1]);
63     }
64     return;
65 }
66 
67 il void work(){
68     for (RG int i=1;i<=5;++i)
69     for (RG int j=1;j<=5;++j){
70         x=gc(); if (x=='*') a[i][j]=3,stx=i,sty=j; else a[i][j]=x-48;
71     }
72     if (check(a)){ printf("0\n"); return; }
73     for (d=1;d<=15;++d){
74     flag=0,dfs(a,stx,sty,0,-1);
75     if (flag){ printf("%d\n",d); return; }
76     }
77     printf("-1\n"); return;
78 }
79 
80 int main(){
81     File("knight");
82     for (RG int i=1;i<=5;++i) goal[1][i]=1;
83     for (RG int i=2;i<=5;++i) goal[2][i]=1;
84     goal[3][3]=3,goal[3][4]=goal[3][5]=goal[4][5]=1;
85     RG int T=gi();
86     while (T--) work();
87     return 0;
88 }

 

N<=8

 

本条明显就是爆搜吧,因为数量比较小。

不过多少丰裕神奇

枚举每场比赛,枚举编号较小的一队的结果,相应的较大的也得以推出结果 
当有某一队剩余比赛全赢也比给定分数低就剪枝 
当有某一队脚下比分领先给定分数也剪枝 
倘使你把那俩个剪枝加上,然后交给,你就会神奇的觉察


干什么如故狂T???


自己依旧too naive,依旧被极限数据卡了。。 
就此要在加二个,当以此部队是和最后一支军队竞赛的时候,只要一种答案,假设和分数相差0,3,1时就搜剩下的二个对应的事态,相差2就剪枝 
。。。我以为这个优化毫无卵用,然而TM居然是有用的。。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 const int stard[4]={3,1,0,0};
 9 
10 int a[17],b[17],n,ans;
11 
12 void dfs(int x,int y)
13 {
14     if (b[x]>a[x]) return ;
15     if (b[x]+(n-y+1)*3<a[x]) return ;
16     if (n==x)
17     {
18         ans++;
19         return;
20     }
21     if (y==n)
22     {
23         int t=a[x]-b[x];
24         if (t==2) return;
25         b[y]+=stard[t];
26         dfs(x+1,x+2);
27         b[y]-=stard[t];
28     }
29     else
30     {
31         b[x]+=3;dfs(x,y+1);b[x]-=3;
32         b[y]+=3;dfs(x,y+1);b[y]-=3;
33         b[x]++,b[y]++;dfs(x,y+1);b[x]--,b[y]--;
34     }
35 }
36 int main()
37 {
38     scanf("%d",&n);
39     for (int i=1;i<=n;i++)
40         scanf("%d",&a[i]);
41     dfs(1,2);
42     printf("%d",ans);        
43 }

 

相关文章