1 /************************************************************** 2     Problem: 1085 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:876 ms 7     Memory:804 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12  13 using namespace std;14 const int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};15 const int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};16 const int last[6][6] = {17 {0, 0, 0, 0, 0, 0},18 {0, 1, 1, 1, 1, 1},19 {0, 0, 1, 1, 1, 1},20 {0, 0, 0, 2, 1, 1},21 {0, 0, 0, 0, 0, 1},22 {0, 0, 0, 0, 0, 0}};23  24 int s[6][6], ans, have_ans, X, Y;25  26 inline bool check(){27     int i, j;28     for (i = 1; i <= 5; ++i)29         for (j = 1; j <= 5; ++j)30             if (s[i][j] != last[i][j]) return 0;31     return 1;32 }33  34 inline bool f(const int &g){35     int h = 0, i, j;36     for (i = 1; i <= 5; ++i)37         for (j = 1; j <= 5; ++j)38             if (s[i][j] != last[i][j] && (++h) + g > ans) return 0;39     return 1;40 }41  42 void dfs(const int &x, const int &y, const int &g){43     if (g == ans){44         if (check()) have_ans = 1;45         return;46     }47     if (have_ans) return;48     int i, X, Y;49     for (i = 0; i < 8; ++i){50         X = x + dx[i], Y = y + dy[i];51         if (X < 1 || Y < 1 || X > 5 || Y > 5) continue;52         swap(s[x][y], s[X][Y]);53         if (f(g)) dfs(X, Y, g + 1);54         swap(s[x][y], s[X][Y]);55     }56 }57  58 int main(){59     int T, i, j;60     scanf("%d", &T);61     char ch;62     while (T--){63         for (i = 1; i <= 5; ++i)64             for (j = 1; j <= 5; ++j){65                 ch = getchar();66                 while (ch != ‘*‘ && ch != ‘0‘ && ch != ‘1‘)67                     ch = getchar();68                 if (ch == ‘*‘)69                     s[i][j] = 2, X = i, Y = j;70                 else s[i][j] = ch - ‘0‘;71             }72         if (check()){73             printf("0\n");74             continue;75         }76         have_ans = 0;77         for (ans = 1; ans <= 15; ++ans){78             dfs(X, Y, 0);79             if (have_ans) break;80         }81         if (have_ans) printf("%d\n", ans);82         else printf("-1\n");83     }84     return 0;85 }