ID A* = ID DFS + 估价函数做可行性剪枝
1. 将搜索的过程视为空格移动的过程;
2. 维护二维数组g[i][j]表示棋盘的状态移动swap即可更新;
3. 每次搜索枚举8个方向
4. 每一步多还原1个棋子, 最后1步至多还原2个棋子;
5. 估价函数: 统计当前棋盘和目标的不同位置个数cnt, 若cnt > depth - u, 则剪枝;
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
const int N = 5;
const int g[N][N] = {
{-1, -1, -1, -1, -1},
{1, -1, -1, -1, -1},
{1, 1, 0, -1, -1},
{1, 1, 1, 1, -1},
{1, 1, 1, 1, 1}
};
int st[N][N], depth;
int get()
{
int cnt = 0;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
if (st[i][j] && st[i][j] != g[i][j]) cnt++;
return cnt;
}
bool dfs(int u, int x, int y)
{
if (!get()) return true;
if (get() > depth - u) return false;
for (int i = 0; i < 8; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 5 && b >= 0 && b < 5)
{
swap(st[x][y], st[a][b]);
if (dfs(u + 1, a, b)) return true;
swap(st[x][y], st[a][b]);
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
char c;
int x, y;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
{
cin >> c;
if (c == '0') st[i][j] = 1;
else if (c == '1') st[i][j] = -1;
else
{
st[i][j] = 0;
x = i, y = j;
}
}
depth = 0;
while (!dfs(0, x, y) && depth < 16) depth++;
if (depth > 15) cout << "-1\n";
else cout << depth << '\n';
}
return 0;
}
1. 每次一次操作, 只有至多3本书的相对发生变化;
2. 估价函数: 比较当前状态和中止状态的差异数, 若超过3 * (depth - u), 则剪枝
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 5;
int g[N];
int backup[M][N];
int n, depth;
int get()
{
int cnt = 0;
for (int i = 0; i < n - 1; i++)
if (g[i] + 1 != g[i + 1]) cnt++;
return (cnt + 2) / 3;
}
bool dfs(int u)
{
if (u + get() > depth) return false;
if (!get()) return true;
for (int len = 1; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++)
{
int r = l + len - 1;
for (int k = r + 1; k < n; k++)
{
memcpy(backup[u], g, sizeof g);
int y = l;
for (int x = r + 1; x <= k; x++, y++) g[y] = backup[u][x];
for (int x = l; x <= r; x++, y++) g[y] = backup[u][x];
if (dfs(u + 1)) return true;
memcpy(g, backup[u], sizeof g);
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n;
for (int i = 0; i < n; i++) cin >> g[i];
depth = 0;
while (depth < 5 && !dfs(0)) depth++;
if (depth > 4) cout << "5 or more\n";
else cout << depth << '\n';
}
return 0;
}
1. 攻击当前矩阵中的颜色数量cnt, 若cnt > depth - u + 1, 剪枝;
2. 更新矩阵: 设操着颜色为c, 则与当前左上角连通块的颜色为c的格子被拓展;
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int N = 10;
int g[N][N], st[N][N];
bool used[N];
int n, depth;
void draw(int x, int y, int c)
{
st[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 1 && a <= n && b >= 1 && b <= n && st[a][b] != 1)
{
st[a][b] = 2;
if (g[a][b] == c) draw(a, b, c);
}
}
}
int get1()
{
memset(used, 0, sizeof used);
int res = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (!used[g[i][j]] && st[i][j] != 1)
{
used[g[i][j]] = true;
res++;
}
return res;
}
int get2(int c)
{
int res = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (g[i][j] == c && st[i][j] == 2)
{
res++;
draw(i, j, c);
}
return res;
}
bool dfs(int u)
{
if (u + get1() > depth) return false;
if (!get1()) return true;
int copy[N][N] = {};
for (int i = 0; i < 6; i++)
{
memcpy(copy, st, sizeof st);
if (get2(i) && dfs(u + 1)) return true;
memcpy(st, copy, sizeof st);
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin >> n, n)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) cin >> g[i][j];
memset(st, 0, sizeof st);
draw(1, 1, g[1][1]);
depth = 0;
while (!dfs(0)) depth++;
cout << depth << '\n';
}
return 0;
}