双向BFS (广搜) (O(8 ^ 7))
看到没有双向BFS的题解我就过来了
这道题也可以用双向(BFS)来做，时间复杂度与(IDA*)不相上下。
双向(BFS)的实现有多种：
- 把初始状态和目标状态扔在一个队列里，每次从队列里搞出来一个扩展
- 把初始状态和目标状态扔在两个队列里，每次选一个队列中元素少的拓展。
- 把初始状态和目标状态扔在两个队列里，每次分别从两个队列中取出一个元素拓展。
这里使用了方法(1)。
时间复杂度分析：每次会扩展(8)个状态，最多扩展(lfloorfrac{15}{2} floor = 7)次（到第八次如果还找不到则肯定超过限制的(15)步，答案则无需扩展），所以复杂度是(O(8 ^ 7))的
具体实现方面看代码。
C++ 代码
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {-2, 2, 2, -2, 1, -1, 1, -1};
//移动方向的打表
int n;
//状态结构体
struct Node{
int v[5][5], f, x, y;
//f = 0 表示从初始状态出发， f = 1 表示从目标状态出发
}s, t, u;
unordered_map<int, int> step[2][30];
// 记录每个状态对应的位置。
int goal[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}
};
//目标状态打表
int start[5][5];
//get(x) 获取状态x的步数
int get(Node x){
int sum = 0;
//把一个位置状态转移成一个二进制数，比较方便。
for(int i = 0; i < 5; i++)
for(int j = 0; j < 5; j++)
if(x.v[i][j] == 1)
sum |= 1 << (i * 5 + j);
if(step[x.f][x.x * 5 + x.y].count(sum) == 0) return INF;
return step[x.f][x.x * 5 + x.y][sum];
}
//set() 设置状态x的步数
void set(Node x, int val){
int sum = 0;
for(int i = 0; i < 5; i++)
for(int j = 0; j < 5; j++)
if(x.v[i][j] == 1)
sum |= 1 << (i * 5 + j);
step[x.f][x.x * 5 + x.y][sum] = val;
}
int bfs(){
queue<Node> q;
q.push(s); q.push(t);
set(s, 0);
set(t, 0);
while(!q.empty()){
Node u = q.front(); q.pop();
//找到同位置的另一状态
Node l = u; l.f = u.f ^ 1;
//如果相遇，代表已经找到一条最短的路径
if(get(u) + get(l) <= 15)
return get(u) + get(l);
//说明所有状态已经都至少走了 8 步， > 最大限制 15
if(get(u) >= 8) break;
l.f = u.f;
for(int i = 0; i < 8; i++){
int nx = u.x + dx[i], ny = u.y + dy[i];
if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
swap(l.v[u.x][u.y], l.v[nx][ny]);
l.x = nx, l.y = ny;
if(get(u) + 1 < get(l)){
set(l, get(u) + 1);
q.push(l);
}
//还原现场
swap(l.v[u.x][u.y], l.v[nx][ny]);
}
}
return -1;
}
int main(){
for(int i = 0; i < 5; i++)
for(int j = 0; j < 5; j++)
t.v[i][j] = goal[i][j];
t.f = 1; t.x = 2; t.y = 2;
int T; scanf("%d", &T);
while(T--){
for(int i = 0; i < 2; i++)
for(int j = 0; j < 30; j++)
step[i][j].clear();
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
char x; cin >> x;
if(x == '*')s.x = i, s.y = j, s.v[i][j] = 2;
else s.v[i][j] = x - '0';
}
}
s.f = 0;
printf("%d
", bfs());
}
return 0;
}