- #include inline void swap(int & x, int & y) {
- int t = x;
- x = y;
- y = t;
- }
- const int map[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
- };
- const int xx[8] = {
- 1,
- 1,
- -1,
- -1,
- 2,
- 2,
- -2,
- -2
- };
- const int yy[8] = {
- 2,
- -2,
- 2,
- -2,
- 1,
- -1,
- 1,
- -1
- };
- int yes = 0,
- a[5][5],
- b[5][5];
- void search(int tot, int to, int x, int y, int num) {
- if (tot == to) {
- if (!num) yes = 1;
- return;
- }
- for (int i = 0; i < 8; i += 1) {
- if (yes) return;
- int tox = x + xx[i],
- toy = y + yy[i];
- int t = num;
- if (tox < 0 || tox > 4 || toy < 0 || toy > 4) continue;
- if (a[x][y] == map[x][y]) num += 1;
- if (a[tox][toy] == map[tox][toy]) num += 1;
- swap(a[x][y], a[tox][toy]);
- if (a[x][y] == map[x][y]) num -= 1;
- if (a[tox][toy] == map[tox][toy]) num -= 1;
- if (num + tot <= to) search(tot + 1, to, tox, toy, num);
- swap(a[x][y], a[tox][toy]);
- num = t;
- }
- }
- int main() {
- int T,
- x,
- y;
- for (scanf("%d", &T); T; T -= 1) {
- for (int i = 0; i < 5; i += 1) for (int j = 0; j < 5; j += 1) {
- char c;
- while (c = getchar(), (c < '0' || c > '1') && c != ' * ');
- if (c != ' * ') a[i][j] = c - '0';
- else {
- a[i][j] = 2;
- x = i;
- y = j;
- }
- }
- int num = 0;
- for (int i = 0; i < 5; i += 1) for (int j = 0; j < 5; j += 1) if (a[i][j] != map[i][j]) num++;
- for (int i = num - 1; i <= 15; i += 1) {
- search(0, i, x, y, num);
- if (yes) {
- printf("%d\n", i);
- break;
- }
- }
- yes ? yes = 0 : printf("-1\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2043558.html