Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 1558
Solved 858

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

搜索+剪枝, 剪枝函数定义为不在该在的位置上的骑士的个数.


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int targ_ans[5][5] = {
    {1, 1, 1, 1, 1},
    {0, 1, 1, 1, 1},
    {0, 0, 2, 1, 1},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0}
};
// Available move sequences
int mov_x[8] = {1,  1,  -1, -1, 2,  2,  -2, -2},
    mov_y[8] = {2,  -2, 2,  -2, 1,  -1, 1,  -1};
bool complete;
int t, res;

// Judge whether this is the final answer, arr[][] represents the colours of the
// pawns, (emp_x, emp_y) represents the coords of the empty position.
bool judge(int arr[5][5], int emp_x, int emp_y)
{
    if (emp_x != 2 || emp_y != 2)
        return false;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            if (arr[i][j] != targ_ans[i][j])
                return false;
    return true;
}

// Cost of further iteration, as in IDA*.
int evaluate(int depth, int step, int arr[5][5])
{
    int req = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            if (arr[i][j] != targ_ans[i][j]) {
                req++;
                if (req + step > depth)
                    return 0;
            }
    return 1;
}

// Search with step #step, in checkerboard arr[][], with (x, y) as the coords of
// the empty position. depth is the largest depth of iteration.
void search(int depth, int step, int arr[5][5], int x, int y)
{ // Unoptimized brute force search.
    // Termination arguments.
    // printf("search %d %d %d %d\n", depth, step, x, y);
    if (step == depth) {
        if (judge(arr, x, y))
            complete = true;
        return ;
    }
    if (complete)
        return ;
    // Iterate reversely, whether this poses potential for another pawn to move
    // to the empty space hither.
    for (int i = 0; i < 8; i++) {
        int newx = x + mov_x[i],
            newy = y + mov_y[i];
        if (newx < 0 || newx > 4 || newy < 0 || newy > 4)
            continue;
        swap(arr[x][y], arr[newx][newy]);
        if (evaluate(depth, step, arr))
            search(depth, step + 1, arr, newx, newy);
        swap(arr[x][y], arr[newx][newy]);
    }
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &t);
    for (int idx = 1; idx <= t; idx++) {
        int arr[5][5];
        int emp_x, emp_y; // The coords of the blank grid position
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++) {
                char ch = ' ';
                while (ch == ' ' || ch == '\r' || ch == '\t' || ch == '\n')
                    scanf("%c", &ch);
                if (ch == '0') arr[i][j] = 0;
                else if (ch == '1') arr[i][j] = 1;
                else arr[i][j] = 2, emp_x = i, emp_y = j;
            }
        // Done readin, searching.
        res = -1;
        complete = false;
        for (int k = 1; k <= 15; k++) {
            // Search and iterate with depth of k.
            search(k, 0, arr, emp_x, emp_y);
            if (complete) {
                res = k;
                break;
            }
        }
        // Outputting data.
        printf("%d\n", res);
    }
    return 0;
}