RT

#7数据在代码下面

#include <bits/stdc++.h>
#define il inline
using namespace std;
int T,sx,sy,mp[6][6];
const int ed[6][6] = {{0,0,0,0,0,0},{0,1,1,1,1,1},{0,0,1,1,1,1},{0,0,0,2,1,1},{0,0,0,0,0,1},{0,0,0,0,0,0}};
const int mvx[8] = {1,1,2,2,-1,-1,-2,-2};
const int mvy[8] = {2,-2,1,-1,2,-2,1,-1};
bool flag;
il void swap(int&x,int&y){int tmp = x;x = y;y = tmp;}
il int gg(){
    int cnt = 0;
    for(int i = 1; i <= 5; i++) for(int j = 1; j <= 5; j++) if(mp[i][j] != ed[i][j]) ++cnt;
    return cnt;
}
il void A_star(int x,int y,int f,int step){
    int g = gg();
    if(!g){
        flag = true;
        return;
    }
    if(g + step > f + 1) return;
    for(int i = 0; i < 8; i++){
        int xx = x + mvx[i],yy = y + mvy[i];
        if(xx > 5 || xx <= 0 || yy > 5 || yy <= 0) continue;
        swap(mp[xx][yy],mp[x][y]);
        A_star(xx,yy,f,step + 1);
        swap(mp[xx][yy],mp[x][y]);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin >> T;
    while(T--){
        for(int i = 1; i <= 5; i++){
            for(int j = 1; j <= 5; j++){
                char ch;
                cin >> ch;
                if(ch == '1') mp[i][j] = 1;
                else if(ch == '0') mp[i][j] = 0;
                else mp[i][j] = 2,sx = i,sy = j;
            }
        }
        for(int i = 1; i <= 15; i++){
            flag = false;
            A_star(sx,sy,i,0);
            if(flag){
                cout << i << endl;
                break;
            }
        }
        if(!flag) puts("-1");
    }
    return 0;
}

数据：

输入：

7
01111
00111
10011
10001
*0000
10111
10111
10001
00101
000*0
11101
000*1
00101
10111
00100
1011*
01101
01111
00001
00001
0101*
11111
00011
01001
00001
11111
01000
10101
00001
01*10
11101
*1101
10010
00101
00100

我的输出：

8
13
10
14
13
-1
-1

正确的输出：

8
13
-1
10
14
-1
13