一. 题目描述
在一个 $5 \\times 5$ 的棋盘上有 $12$ 个白色的骑士和 $12$ 个黑色的骑士,且有一个空位。
在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为 $1$,纵坐标相差为 $2$ 或者横坐标相差为 $2$,纵坐标相差为 $1$ 的格子)移动到空位上。
给定一个初始的棋盘,怎样才能经过移动变成如下目标棋盘:为了体现出骑士精神,他们必须以最少的步数完成任务。
输入格式
第一行有一个正整数 $T$,表示一共有 $T$ 组数据。
接下来有 $T$ 个 $5×5$ 的矩阵,$0$ 表示白色骑士,$1$ 表示黑色骑士,*
表示空位。
两组数据之间没有空行。
输出格式
每组数据输出占一行。
如果能在 $15$ 步以内(包括 $15$ 步)到达目标状态,则输出步数,否则输出 $\-1$。
数据范围
$1 \\le T \\le 10$
输入样例:
2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100
输出样例:
7
二. 算法
1. IDA*算法
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
vector<vector<char>> g; // 初始地图
int x, y; // 初始起点
int dx[8] = {2, 1, 2, 1, -1, -2, -1, -2}, dy[8] = {-1, -2, 1, 2, 2, 1, -2, -1}; // 偏移量
int depth; // 迭代深度
int fun() // 估价函数
{
int re = 0;
for(int i = 0; i < 5; i ++ )
for(int j = 0; j < 5; j ++ )
{
if(g[i][j] == '1')
{
if(i == j && (i == 3 || i == 4)) re ++ ;
if(j < i) re ++ ;
}
else if(g[i][j] == '0')
{
if(i == j && (i == 0 || i == 1)) re ++ ;
if(j > i) re ++ ;
}
else
{
if(i != 2 || j != 2) re ++ ;
}
}
return re;
}
bool DFS(int u, int x1, int y1, int x2, int y2) // 参数: 当前步数, 空位横坐标, 空位纵坐标, 上一步横坐标, 上一步纵坐标
{
int t = fun();
if(!t) return true;
if(u + t > depth) return false; // 迭代加深和IDA*的应用, 若 当前步数+预估最小步数 超过到所规定的最大层数, 则递归返回
for(int i = 0; i < 8; i ++ )
{
int x = x1 + dx[i], y = y1 + dy[i];
if(x < 0 || y < 0 || x >= 5 || y >= 5) continue;
if(x == x2 && y == y2) continue;
swap(g[x][y], g[x1][y1]);
if(DFS(u + 1, x, y, x1, y1)) return true;
swap(g[x][y], g[x1][y1]); // 恢复现场
}
return false;
}
void solve()
{
g.clear();
depth = 0;
char t;
for(int i = 0; i < 5; i ++ )
{
vector<char> temp;
for(int j = 0; j < 5; j ++ )
{
cin >> t;
temp.push_back(t);
if(t == '*') x = i, y = j;
}
g.push_back(temp);
}
while(depth <= 15 && !DFS(0, x, y, -1, -1)) depth ++ ;
if(depth > 15) cout << -1 << endl;
else cout << depth << endl;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while(T -- ) solve();
return 0;
}
2. A*算法
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
struct state
{
int dist1; // 预估步数 + 当前步数
int dist2; // 当前步数
vector<vector<char>> g; // 地图, 即状态
PII idx; // 空位
};
struct cmp // 比较函数
{
bool operator () (const state &a, const state &b)
{
return b.dist1 <= a.dist1;
}
};
vector<vector<char>> g; // 初始地图
PII start; // 初始起点
int dx[8] = {2, 1, 2, 1, -1, -2, -1, -2}, dy[8] = {-1, -2, 1, 2, 2, 1, -2, -1}; // 偏移量
int fun(vector<vector<char>> &g) // 估价函数
{
int re = 0;
for(int i = 0; i < 5; i ++ )
for(int j = 0; j < 5; j ++ )
{
if(g[i][j] == '1')
{
if(i == j && (i == 3 || i == 4)) re ++ ;
if(j < i) re ++ ;
}
else if(g[i][j] == '0')
{
if(i == j && (i == 0 || i == 1)) re ++ ;
if(j > i) re ++ ;
}
else
{
if(i != 2 || j != 2) re ++ ;
}
}
return re;
}
int Astar() // A*算法
{
priority_queue<state, vector<state>, cmp> heap;
map<vector<vector<char>>, bool> st;
map<vector<vector<char>>, int> dist;
heap.push({fun(g), 0, g, start});
while(heap.size())
{
auto t = heap.top(); heap.pop();
if(st[t.g]) continue;
st[t.g] = 1;
if(t.dist1 == t.dist2) return t.dist2;
int x1 = t.idx.x, y1 = t.idx.y;
int dist2 = t.dist2 + 1;
for(int i = 0; i < 8; i ++ )
{
int x2 = x1 + dx[i], y2 = y1 + dy[i];
if(x2 < 0 || y2 < 0 || x2 >= 5 || y2 >= 5) continue;
auto g = t.g;
swap(g[x1][y1], g[x2][y2]);
int estimate = fun(g);
if(estimate + dist2 > 15) continue; // A*算法的应用, 若 预估步数+当前步数 > 题目限制步数, 则不加入堆中
if((dist.count(g) == 0) || (dist[g] > dist2))
{
dist[g] = dist2;
heap.push({estimate + dist2, dist2, g, {x2, y2}});
}
}
}
return -1;
}
void solve()
{
g.clear();
char t;
for(int i = 0; i < 5; i ++ )
{
vector<char> temp;
for(int j = 0; j < 5; j ++ )
{
cin >> t;
temp.push_back(t);
if(t == '*') start.x = i, start.y = j;
}
g.push_back(temp);
}
cout << Astar() << endl;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while(T -- ) solve();
return 0;
}
3. 优化后的A*算法(200+ ms)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef pair<PII, string> PIS;
#define x first
#define y second
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
string aim = {'1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '0', '0', '*', '1', '1', '0', '0', '0', '0', '1', '0', '0', '0', '0', '0'};
string s;
int T, start;
unordered_map<string, int> dist;
// unordered_map<string, bool> st;
int fun(string &s)
{
int cnt = 0;
for (int i = 0; i < 25; i ++ )
if (aim[i] != s[i]) cnt ++ ;
return cnt;
}
int AStar()
{
priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
heap.push({{fun(s), start}, s});
dist[s] = 0;
while(heap.size())
{
auto t = heap.top(); heap.pop();
// if(st[t.y]) continue; 加判重后运行更慢
// st[t.y] = true;
string g = t.y; int d = dist[g], pos = t.x.y;
if (g == aim) return d;
for (int i = 0; i < 25; i ++ )
if (g[i] == '*') { pos = i; break; }
int px = pos / 5, py = pos - 5 * px;
for (int i = 0; i < 8; i ++ )
{
int x = px + dx[i], y = py + dy[i];
if (x < 0 || x >= 5) continue;
if (y < 0 || y >= 5) continue;
string temp = g;
swap(temp[pos], temp[x * 5 + y]);
if ((dist.count(temp) == 0) || (dist[temp] > d + 1))
{
int t = d + 1 + fun(temp);
if(t > 16) continue;
dist[temp] = d + 1;
heap.push({{t, x * 5 + y}, temp});
}
}
}
return -1;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
dist.clear(); s.clear(); //st.clear();
string temp;
for (int i = 0; i < 5; i ++ )
{
cin >> temp;
s += temp;
}
for(int i = 0; i < 25; i ++ )
if(s[i] == '*') start = i;
printf("%d\n", AStar());
}
return 0;
}