Bzoj 1085(IDA*)

Bzoj 1085
这种限制步数的题目可以用迭代加深搜索做。并且这种只有一个空格的题目,一般就是用空格的坐标去遍历其他有东西的坐标,然后相当于东西的移动。
本题直接DFS超时严重,样例都过不了。
我们考虑加一个估价函数剪枝:当前步数$+$当前状态和目标状态棋盘上的差异数(具体看代码)$<$迭代加深的步数
之后就很快了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 5;
const int gl[MAXN + 2][MAXN + 2] = {
{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 dx[8] = {1, 2, -1, 2, -2, 1, -1, -2};
const int dy[8] = {2, 1, 2, -1, 1, -2, -2, -1};
int a[MAXN + 2][MAXN + 2];
int kx, ky, flag;
char s[MAXN];
bool check() {
if (a[2][2] != 2) return false;
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++) if (gl[i][j] != a[i][j]) return false;
return true;
}
bool gv(int st, int k) {
int tot = 0;
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++) if (gl[i][j] != a[i][j]) tot++;
if (st + tot > k) return false;
return true;
}
void dfs(int x, int y, int st, int k) {
if (flag) return ;
if (check()) {flag = true; return ;}
if (st >= k) return ;
for (int i = 0; i < 8; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx >= 0 && ty >= 0 && tx < MAXN && ty < MAXN) {
swap(a[x][y], a[tx][ty]);
if (gv(st, k)) dfs(tx, ty, st + 1, k);
swap(a[x][y], a[tx][ty]);
}
}
}
void clean() {
flag = kx = ky = 0, ms(a, 0);
}
void solve() {
clean();
for (int i = 0; i < MAXN; i++) {
scanf("%s", s);
for (int j = 0; j < MAXN; j++) {
if (s[j] == '0') a[i][j] = 0; else if (s[j] == '1') a[i][j] = 1; else if (s[j] == '*') a[i][j] = 2, kx = i, ky = j;
}
}
for (int i = 1; i <= 15; i++) {
dfs(kx, ky, 0, i);
if (flag) {
printf("%d\n", i);
return ;
}
}
if (!flag) printf("-1\n");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}

------ 本文结束 ------