八数码—unordered哈希表即记录步骤—A*算法—曼哈顿距离—BFS

在一个 3×3 的网格中，1∼8 这 8 个数字和一个 X 恰好不重不漏地分布在这 3×3的网格中。

例如：

1 2 3
X 4 6
7 5 8

在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 X

例如，示例中图形就可以通过让 X 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
X 4 6   4 X 6   4 5 6   4 5 6
7 5 8   7 5 8   7 X 8   7 8 X

把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式

输入占一行，将 3×3的初始网格描绘出来。例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8 

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。如果答案不唯一，输出任意一种合法方案即可。如果不存在解决方案，则输出 unsolvable。

输入样例：

2  3  4  1  5  x  7  6  8 

输出样例

ullddrurdllurdruldr

 

 分析：如果逆序对数量是奇数则无解；则双层for循环判断即可；

A*写法

#include 
#include 
#include 
#include 
#include 
using namespace std;
// 估计函数，计算至少还要几步才能到target board。 
// 每次移动一步只能让水平或者竖直方向挪动一格。
// 所以对比当前board和target board，看看每一位和目标位差多少曼哈顿距离。
// 注意这里x不算，所以每次移动只能把非x能往正确的位置移动一步。
// 当所有数字都到位了，x也自然到位。
int f(string state)//求曼哈顿距离
{
    int res = 0;
    for (int i = 0; i < state.size(); i++) {
        if (state[i] == 'x')
            continue;
        //数字应该在的位置
        int x = i / 3;
        int y = i % 3;
        //数字的当前位置
        int nx = (state[i] - '1') / 3;
        int ny = (state[i] - '1') % 3;
        res += abs(x - nx) + abs(y - ny);
    }
    return res;
}
 
string bfs(string start)
{
    int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
    char op[4] = { 'u', 'r', 'd', 'l' };
    string end = "12345678x";
 
    unordered_mapint> dist;//存真实距离
    unordered_mapchar>> pre;//存步骤
    priority_queueint, string>, vectorint, string>>, greaterint, string>>> q;//存估计距离+当前状态
 
    q.push({ f(start)+0, start });//估计值=从起点到这个点的真实距离加上到终点的估计距离。
    dist[start] = 0;
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        //当前操作的字符串
        string now = t.second;
        //出口
        if (now == end) break;
        //真实最短距离
        int x, y;
        for (int i = 0; i < now.size(); i++)
            if (now[i] == 'x')
            {
                x = i / 3, y = i % 3;
                break;
            }
        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(now[x * 3 + y], now[a * 3 + b]);
                string next = now;
                swap(now[x * 3 + y], now[a * 3 + b]);
                if (!dist.count(next) || dist[next]>dist[now]+1)
                    //这是A*算法，除了终点之外，当第一次搜到某个点的时候，距离不一定是最短的，
                    //其dist[]的值是不断变小的，所以要加后一个判断。
                    //dis[now]+f(now);只要估计距离小于或者等于真实距离，
                    //那么状态now第一次从队列中出来的时候它的距离就一定是最短距离了；
                {
                    dist[next] = dist[now] + 1;
                    pre[next] = { now, op[i] };
                    q.push({ dist[next] + f(next), next });//当前的真实植加上估计值
                }
            }
        }
    }
 
    string res;
    //输出步数
    while (end != start)
    {
        res += pre[end].second;
        end = pre[end].first;
    }
    reverse(res.begin(), res.end());
    return res;
}
 
int main()
{
    string g, c, seq;
    while (cin >> c)
    {
        g += c;
        if (c != "x") seq += c;
    }
    //判断无解情况；
    int t = 0;
    for (int i = 0; i < seq.size(); i++)
        for (int j = i + 1; j < seq.size(); j++)
            if (seq[i] > seq[j])
                t++;
    if (t % 2) puts("unsolvable");
    else cout << bfs(g) << endl;
    return 0;
}

简单BFS写法

#include 
#define endl '\n'
#define int long long
#include
#define Bug cout<<"---------------------"<
using namespace std;
constexpr int N = 10;
char arr[N];
string ed = "12345678x";
string st;
//数据结构
//存步数
//unordered_mapdis;
unordered_mapchar, string> >pre;//存步骤
int dx[4] = { -1,0,0,1 }; int dy[4] = { 0,1,-1,0 };//分别对应上，右，左，下
void bfs() {
	queueq;
	q.push(st);
	//dis[st] = 0;
	while (q.size()) {
		string now = q.front();
		q.pop();
		//if (now == ed) return dis[now];
		if (now == ed) return ;
		int pos = now.find('x');
		int x = pos / 3, y = pos % 3;
		for (int i = 0;i < 4;i++) {
			int tx = x + dx[i];
			int ty = y + dy[i];
			if (tx >= 3 || tx < 0 || ty < 0 || ty >= 3) {
				continue;
			}
			swap(now[pos], now[tx * 3 + ty]);
			string next = now;
			swap(now[pos], now[tx * 3 + ty]);
			if (!pre.count(next)) {
				//dis[next] = dis[now] + 1;
				if (i == 0) {
					pre[next] = { 'u',now };
				}
				else if (i == 1) {
					pre[next] = { 'r',now };
				}
				else if (i == 2) {
					pre[next] = { 'l',now };
				}
				else{
					pre[next] = { 'd',now };
				}
				q.push(next);
			}
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//读入
	string x;
	for (int i = 0;i < 9;i++) {
		char c;
		cin >> c;
		st += c;
		if (c != 'x') x += c;
	}
	int cnt = 0;//统计逆序对的数量
	for (int i = 0;i < 8;i++)
		for (int j = i + 1;j < 8;j++)
			if (x[i] > x[j])
				cnt++;
	if (cnt % 2) 
	{
		printf("unsolvable\n");//如果逆序对为奇数,就不可能抵达终点
		return 0;
	}
	//搜索
	bfs();
	//输出最小步数
	//cout << ans << endl;
	//使用递推出结果
	string res;
	while (st != ed) {
		res += pre[ed].first;
		ed = pre[ed].second;
	}
	//是从结尾开始找，所以需要反转一下
	reverse(res.begin(), res.end());
	cout << res << endl;
	return 0;
}