题解【洛谷P1379】八数码难题

典型的\(\text{BFS}\)。

双向广搜是一种对\(\text{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\)的排列，然后\(\text{BFS}\)时队列里存储当前\(9\)位状态在所有排列里的下标，将\(9\)位整数转成\(3 \times 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\n", bfs()); //输出答案

	return 0;

}

其实这题还有一种使用\(\text{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\n", d); break;} //搜到了结果

	}

	return 0;

}

巴特西

题解【洛谷P1379】八数码难题

最新文章

热门文章