信息学奥赛一本通T1449-魔板-3种扩展方式

解题思路:
3种扩展方式而已

参考代码:

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <queue>

#define x first
#define y second

using namespace std;

unordered_map<string, int> dist;
unordered_map<string, pair<char, string>> pre;
string st = "12345678", ed, res;

string move0(string s)
{
	for (int i = 0; i < 4; i++) swap(s[i], s[7-i]);
	return s;
}

string move1(string s)
{
	for (int i = 0; i < 3; i++) swap(s[3], s[i]);
	for (int i = 4; i < 7; i++) swap(s[i], s[i+1]);
	return s;
}

string move2(string s)
{
	swap(s[1], s[2]), swap(s[5], s[6]), swap(s[1], s[5]);
	return s;
}

void bfs()
{
	queue<string> q;
	q.push(st);
	dist[st] = 0;
	while (!q.empty())
	{
		string t = q.front();
		q.pop();
		if (t == ed) return ;
		string m[3];
		m[0] = move0(t);
		m[1] = move1(t);
		m[2] = move2(t);
		for (int i = 0; i < 3; i++)
			if (!dist.count(m[i])) 
			{
				q.push(m[i]);
				dist[m[i]] = dist[t] + 1;
				pre[m[i]] = {'A' + i, t}; // second经过first操作到达m[i] 
			}
	}
}

int main()
{
	for (int i = 1; i <= 8; i++)
	{
		char ch;
		cin >> ch;
		ed += ch;
	}
	bfs();
	cout << dist[ed] << endl;
	if (dist[ed])
	{
		while (ed != st)
		{
			res += pre[ed].x;
			ed = pre[ed].y;
		}
		reverse(res.begin(), res.end());
		cout << res << endl;
	}
	return 0;
}