bzoj1085骑士精神 A*

A*搜索实际上只有空格再走

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<algorithm>
 8 #define rep(i,l,r) for(int i=l;i<r;i++)
 9 #define clr(a,x) memset(a,x,sizeof(a))
10 #define legal(x,y) (x<n&&0<=x&&y<n&&0<=y)
11 using namespace std;
12 const int n=5;
13 const int g[n][n]={{1,1,1,1,1}
14                   ,{0,1,1,1,1}
15                   ,{0,0,2,1,1}
16                   ,{0,0,0,0,1}
17                   ,{0,0,0,0,0}};
18 const int dir[8][2]={{1,2},{2,1},{1,-2},{-2,1},{-1,2},{2,-1},{-1,-2},{-2,-1}};
19 int now[n][n],ans;
20 bool flag;
21 bool same()
22 {
23     rep(i,0,n)
24         rep(j,0,n)
25             if(now[i][j]!=g[i][j]) return 0;
26     return 1;
27 }
28 bool estimate(int d)
29 {
30     rep(j,0,n)
31         rep(k,0,n)
32             if(now[j][k]!=g[j][k]) 
33             if(++d>ans) return 0;
34     return 1;
35 }
36 int cnt=0;
37 void dfs(int x,int y,int d)
38 {        
39     if(d==ans&&same()){
40         flag=1;
41         return;
42     }
43     if(flag) return;
44     rep(i,0,8){
45         int x1=x+dir[i][0],y1=y+dir[i][1];
46         if(legal(x1,y1)){
47             swap(now[x][y],now[x1][y1]);
48             if(estimate(d)) dfs(x1,y1,d+1);
49             swap(now[x][y],now[x1][y1]);
50         }
51     }
52 }
53 int main()
54 {    
55     int t;
56     cin>>t;
57     while(t--){
58         clr(now,0);
59         int x,y;
60         flag=0;
61         rep(i,0,n) 
62             rep(j,0,n){
63                 char c=getchar();
64                 while(c!='*'&&!isdigit(c)) c=getchar();
65                 if(c=='*') now[x=i][y=j]=2;
66                 else now[i][j]=c-'0';
67         }
68         for(ans=1;ans<=15;ans++){
69             dfs(x,y,0);
70             if(flag) break;
71         }
72         printf("%d
",flag?ans:-1);
73     }
74     return 0;
75 }

View Code

1085: [SCOI2005]骑士精神

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1110 Solved: 602
[Submit][Status][Discuss]

Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：为了体现出骑士精神，他们必须以最少的步数完成任务。

Input

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

Output

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

Sample Input

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100

Sample Output

7
-1

HINT

Source

[Submit][Status][Discuss]