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
Solution
裸的搜索一定超时。我们用一下A*
令估价函数$f(n) = g(n) + h(n)$,其中$g(n)$表示当前递归深度,$h(n)$表示目前的棋盘和目标棋盘有多少个格子是不一样的
那么$f(n) > ans$时就不用在搜下去了。
1 #include2 using namespace std; 3 const char s2[5][6] = { { "11111"}, { "01111"}, { "00*11"}, { "00001"}, { "00000"}}; 4 char s1[5][5]; 5 int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1}; 6 int dy[8] = { 2, 1, -1, -2, -2, -1, 1, 2}; 7 int ans; 8 9 bool check_same()10 {11 for(int i = 0; i < 5; i++)12 for(int j = 0; j < 5; j++)13 if(s1[i][j] != s2[i][j]) return false;14 return true;15 }16 17 int astar(int dep)18 {19 for(int i = 0; i < 5; i++)20 for(int j = 0; j < 5; j++)21 if(s1[i][j] != s2[i][j]) dep++;22 return dep;23 }24 25 void DFS(int dep)26 {27 int x, y;28 if(check_same()) ans = min(ans, dep - 1);29 if(dep >= ans) return;30 for(int i = 0; i < 5; i++)31 for(int j = 0; j < 5; j++)32 if(s1[i][j] == '*') x = i, y = j;33 for(int i = 0; i < 8; i++)34 {35 x += dx[i], y += dy[i];36 if(x > -1 && x < 5 && y > -1 && y < 5)37 {38 swap(s1[x][y], s1[x - dx[i]][y - dy[i]]);39 if(astar(dep) <= ans) DFS(dep + 1);40 swap(s1[x][y], s1[x - dx[i]][y - dy[i]]);41 }42 x -= dx[i], y -= dy[i];43 }44 }45 46 int main()47 {48 int t;49 cin >> t;50 while(t--)51 {52 ans = 16;53 for(int i = 0; i < 5; i++)54 for(int j = 0; j < 5; j++)55 cin >> s1[i][j];56 DFS(1);57 cout << (ans == 16 ? -1 : ans) << endl;58 }59 return 0;60 }