题目链接：https://www.luogu.com.cn/problem/P2324
解题思路：
A* 搜索。
(h(x)) 表示当前状态下有多少位置和目标状态不一样。
示例代码：
#include <bits/stdc++.h>
using namespace std;
const int target[][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
};
struct Matrix {
int a[5][5];
int to_ll() {
long long res = 0, t = 1;
for (int i = 0; i < 25; i ++) {
res += a[i/5][i%5] * t;
t *= 3;
}
return res;
}
};
int h(Matrix a) {
int cnt = 0;
for (int i = 0; i < 5; i ++)
for (int j = 0; j < 5; j ++)
if (a.a[i][j] != target[i][j])
cnt ++;
return cnt;
}
struct Node {
Matrix a;
int step;
bool operator < (Node b) const {
return step + h(a) > b.step + h(b.a);
}
};
priority_queue<Node> que;
set<long long> st;
int T;
char s[5][10];
int dir[8][2] = { -1, -2, -1, 2, -2, -1, -2, 1, 1, -2, 1, 2, 2, -1, 2, 1 };
inline bool in_map(int x, int y) {
return x >= 0 && x < 5 && y >= 0 && y < 5;
}
bool check(Node u) {
for (int i = 0; i < 5; i ++)
for (int j = 0; j < 5; j ++)
if (u.a.a[i][j] != target[i][j])
return false;
return true;
}
int main() {
scanf("%d", &T);
while (T --) {
while (!que.empty()) que.pop();
st.clear();
for (int i = 0; i < 5; i ++) scanf("%s", s[i]);
Node u;
for (int i = 0; i < 5; i ++) for (int j = 0; j < 5; j ++) {
if (s[i][j] == '*') u.a.a[i][j] = 2;
else u.a.a[i][j] = s[i][j] - '0';
}
u.step = 0;
bool flag = false;
que.push(u);
int cnt = 0;
while (!que.empty()) {
Node u = que.top();
que.pop();
if (check(u)) {
flag = true;
printf("%d
", u.step);
break;
}
if (u.step + h(u.a)-1 > 15) continue; // 这句话最重要!!!
int x, y;
for (int i = 0; i < 5; i ++) for (int j = 0; j < 5; j ++)
if (u.a.a[i][j] == 2) x = i, y = j;
for (int i = 0; i < 8; i ++) {
int xx = x + dir[i][0], yy = y + dir[i][1];
if (!in_map(xx, yy)) continue;
Node v = { u.a, u.step+1 };
swap(v.a.a[x][y], v.a.a[xx][yy]);
int val = v.a.to_ll();
if (st.count(val)) continue;
st.insert(val);
que.push(v);
}
}
if (!flag) puts("-1");
}
return 0;
}