典型的( ext{BFS})。
双向广搜是一种对( ext{BFS})的优化，它适用于起点和终点都明确的题目。
这里给出我的双向广搜模板。
inline int bfs()//双向广搜
{
q.push(s), f[s] = 1;
q.push(t), f[t] = -1;
//队列初始化
//f数组表示这个状态时从起点来还是从终点来
//f[i]为正数就是从起点来
//f[i]为负数就是从终点来
while (!q.empty())//如果队列不为空
{
int u = q.front(); //取出队首元素
q.pop();//弹出队首
...
for (...)
{
int tmp;//tmp是可以转移的状态
...
if (!f[tmp]) //如果没有访问过这个元素
{
f[tmp] = f[u] + f[u] / abs(f[u]);//这个操作很巧妙,它可以让正数+1，负数-1
q.push(tmp);//将tmp装进队列
}
else if (f[tmp] * f[u] < 0) //乘积<0说明不是同号,来源不同
{
return abs(f[tmp] - f[u]) - 1;//直接返回答案,注意要-1
}
}
}
return -1;//返回-1说明出了问题，需要Debug
}
回到这一题，我们需要从小到大预处理处(0 sim 8)的排列，然后( ext{BFS})时队列里存储当前(9)位状态在所有排列里的下标，将(9)位整数转成(3 imes 3)的地图，找到为(0)的位置，将它与上下左右的四个位置交换，再将地图转成整数，放入队列中。
由于在本题中起点和终点都很明确（起点是输入的(9)位整数，终点是123804765），因此可以使用双向广搜优化。
完整代码：
#include <bits/stdc++.h>
#define itn int
#define gI gi
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int maxn = 3628803;
int n, m, id[maxn], cnt, usd[10], f[maxn], mp[5][5], xx, yy;
queue <int> q;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline void getditu(int x) //将9位整数转换成3*3的地图
{
for (int i = 3; i >= 1; i-=1) //记得倒叙循环
{
for (int j = 3; j >= 1; j-=1) //记得倒叙循环
{
mp[i][j] = x % 10, x /= 10;
if (mp[i][j] == 0) xx = i, yy = j; //处理0的位置
}
}
}
inline int getid() //将地图转换成9位数字
{
int uu = 0;
for (int i = 1; i <= 3; i+=1)
{
for (int j = 1; j <= 3; j+=1) uu = uu * 10 + mp[i][j];
}
return uu;
}
inline bool check(int x, int y) //判断当前位置在不在地图内
{
return x >= 1 && x <= 3 && y >= 1 && y <= 3;
}
void dfs(int now, int s) //从小到大预处理排列
{
if (now == 10) //搜完了
{
id[++cnt] = s; //存储排列
return; //记得返回
}
for (int i = 0; i <= 8; i+=1) //从小到大维护有序性
{
if (!usd[i]) //没有记录过
{
usd[i] = 1; //标记
dfs(now + 1, s * 10 + i); //搜索下一层
usd[i] = 0; //回溯
}
}
}
inline int erfen(int x) //二分x在所有排列中的下标
{
int l = 1, r = cnt, ans = 0;
while (l <= r)
{
int mid = (l + r) >> 1;
if (id[mid] == x) {ans = mid; break;}
else if (id[mid] < x) l = mid + 1;
else r = mid - 1;
}
return ans;
}
int s, t;
inline int bfs() //双向广搜
{
q.push(erfen(s)), f[erfen(s)] = 1;
q.push(erfen(t)), f[erfen(t)] = -1;
//记得存储的是下标
while (!q.empty()) //队列不为空
{
int u = q.front(); q.pop(); //弹出队头
getditu(id[u]); //转换为地图
for (int i = 0; i < 4; i+=1) //枚举上下左右四个方向
{
if (check(xx + dx[i], yy + dy[i]))
{
swap(mp[xx][yy], mp[xx + dx[i]][yy + dy[i]]); //交换
int tmp = erfen(getid()); //要转移的状态
if (!f[tmp]) //没有访问过
{
f[tmp] = f[u] + f[u] / abs(f[u]); //记录
q.push(tmp); //装进队列
}
else if (f[tmp] * f[u] < 0) //找到答案了
{
return abs(f[tmp] - f[u]) - 1; //返回答案
}
swap(mp[xx][yy], mp[xx + dx[i]][yy + dy[i]]); //记得换回
}
}
}
return -1;
}
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
s = gi(), t = 123804765; //s为起点,t为终点
if (s == t) {puts("0"); return 0;} //特判起点终点相同的情况
dfs(1, 0); //预处理出排列
printf("%d
", bfs()); //输出答案
return 0;
}
其实这题还有一种使用( ext{IDA*})的做法。
由于博主太懒，所以直接放代码啦。
我把估价函数设为当前地图与目标状态地图有几处不同。
#include <bits/stdc++.h>
#define itn int
#define gI gi
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
int x, n, d, pp[5][5], ap[5][5], pd, xx, yy;
const int dx[] = {1, 0, 0, -1}, dy[] = {0, 1, -1, 0};
inline bool check()
{
for (int i = 1; i <= 3; i+=1) for (int j = 1; j <= 3; j+=1)
{
if (pp[i][j] != ap[i][j]) return false;
}
return true;
}
inline bool chk(int x, int y) {return x >= 1 && x <= 3 && y >= 1 && y <= 3;}
inline bool test_A_xing(int now) //估价函数
{
int cnt = 0;
for (int i = 1; i <= 3; i+=1) for (int j = 1; j <= 3; j+=1)
{
if (ap[i][j] != pp[i][j]) if ((++cnt) + now > d) return false;
}
return true;
}
void A_xing(int now, int x, int y, int lst)
{
if (now == d) {if (check()) pd = 1; return;}
if (pd) return;
for (int i = 0; i < 4; i+=1)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > 3 || ny < 1 || ny > 3 || lst + i == 3/*避免走重复的路*/) continue;
swap(ap[x][y], ap[nx][ny]);
if (test_A_xing(now) && !pd) A_xing(now + 1, nx, ny, i);
swap(ap[x][y], ap[nx][ny]);
}
}
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
x = gi();
for (int i = 0; i < 9; i+=1)
{
int y = x % 10;
x /= 10;
ap[i / 3 + 1][i % 3 + 1] = y;
if (y == 0) xx = i / 3 + 1, yy = i % 3 + 1;
}
int t = 123804765;
for (int i = 0; i < 9; i+=1)
{
int y = t % 10;
pp[i / 3 + 1][i % 3 + 1] = y;
t /= 10;
}
if (check()) {puts("0"); return 0;}
for (d = 1; ; d+=1) //迭代加深
{
A_xing(0, xx, yy, -1); //A*搜索
if (pd) {printf("%d
", d); break;} //搜到了结果
}
return 0;
}