Solution

迭代加深搜索

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int a[5][5], now[5][5];
int go[8][2] = {
    {2, -1}, {-1, 2},
    {-2, 1}, {1, -2},
    {-1, -2}, {-2, -1},
    {2, 1}, {1, 2}
};
int target[5][5] = {
    {1, 1, 1, 1, 1},
    {0, 1, 1, 1, 1},
    {0, 0, -1, 1, 1},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0}
};
bool check(int x, int y) {
    return x >= 0 && x <= 4 && y >= 0 && y <= 4;
}
int getdiff() {
    int cnt = 0;
    for(int i=0; i<5; i++)
    for(int j=0; j<5; j++) {
        if(now[i][j] != target[i][j])
            cnt++;
    }
    return cnt;
}
int ans, flag;
void dfs(int x, int y, int step, int limit) {
    int cnt = getdiff();
    if(cnt == 0) {
        ans = step;
        return;
    }
    if(step + cnt - 1> limit) return;
    for(int i=0; i<8; i++) {
        int tx = x + go[i][0];
        int ty = y + go[i][1];
        if(!check(tx, ty)) continue;
        swap(now[x][y], now[tx][ty]);
        dfs(tx, ty, step+1, limit);
        swap(now[x][y], now[tx][ty]);
    }
}
void solve() {
    int x, y;
    for(int i=0; i<5; i++)
    for(int j=0; j<5; j++) {
        char c; cin >> c;
        if(c == '*') {
            x = i; y = j;
            a[i][j] = -1;
            continue;
        }
        a[i][j] = c - '0';
    }
    
    for(int i=0; i<=15; i++) {
        flag = false, ans = 1e9;
        for(int j=0; j<5; j++)
        for(int k=0; k<5; k++)
            now[j][k] = a[j][k];
        dfs(x, y, 0, i);
        if(i == ans) break;
    }
    printf("%d\n", ans == 1e9 ? -1 : ans);
}
int main() {
    int T; scanf("%d", &T);
    while(T--) solve();
    return 0;
}

Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士, 且有一个空位。在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为1,纵坐标相差为2或者横坐标相差为2,纵坐标相差为1的格子)移动到空位上。 给定一个初始的棋盘,怎样才能经过移动变成如下目标棋盘:

aa.jpg

为了体现出骑士精神,他们必须以最少的步数完成任务。

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