见注释

#include <bits/stdc++.h>

#define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
//typedef long long int ll;
char goal[5][5] = {
        {'1', '1', '1', '1', '1'},
        {'0', '1', '1', '1', '1'},
        {'0', '0', '*', '1', '1'},
        {'0', '0', '0', '0', '1'},
        {'0', '0', '0', '0', '0'}
};//目标的棋盘情况
char cur[5][5];//当前的棋盘情况
//骑士是走日字形的，我们把它的八种方向存储起来，方便待会遍历
int movex[8] = {1, 1, 2, 2, -1, -1, -2, -2};
int movey[8] = {2, -2, 1, -1, 2, -2, 1, -1};
int T;//测试用例数
int spacex, spacey;//存储当前空格的所在位置
int depth;//当前允许的步数
int getdata() {//获取当前的空格所在位置，和当前棋盘情况与目标棋盘情况的不同的位置数目
    int num = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (cur[i][j] == '*') {
                spacex = i;
                spacey = j;
            }
            if (cur[i][j] != goal[i][j]) {
                num++;
            }
        }
    }
    return num;
}

bool dfs(int cur_depth) {
    int difnum = getdata();//当前棋盘情况与目标棋盘情况的不同的位置的数目
    int nowx = spacex, nowy = spacey;//记录下来
    if (cur_depth + difnum - 1 > depth) return false;//不同的位置过于的多，而我们每移动一步，至多只能把一个位置变得合理
    if (!difnum) return true;//没有不同的位置了
    for (int i = 0; i < 8; i++) {
        int posx = nowx + movex[i], posy = nowy + movey[i];
        if (posx < 0 || posy < 0 || posx > 4 || posy > 4) continue;//超出边界
        swap(cur[posx][posy], cur[nowx][nowy]);//模拟移动
        if (dfs(cur_depth + 1)) return true;//如果可行，则返回
        swap(cur[posx][posy], cur[nowx][nowy]);//还原这次移动之前的情况，避免影响下一次的模拟
    }
    return false;
}

int main() {
    FIO;
    cin >> T;
    while (T--) {
        for (auto & i : cur) cin >> i;
        depth = 0;//深度，也即现在所走的步数
        while (depth <= 15 && !dfs(0)) depth++;
        if (depth == 16) cout << "-1" << endl;
        else cout << depth << endl;
    }
    return 0;
}