经典题：map写bfs

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
int order[8] = { 4,1,2,3,6,7,8,5 };
int order2[8] = { 1,7,2,4,5,3,6,8 };
map<string, int>dist;
map<string, pair<char, string>>pre;
string start, en;
queue<string> q;
string move1(string t)
{
	for (int i = 0; i < 4; i++) swap(t[i], t[7 - i]);
	return t;
}

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

string move3(string t)
{
	swap(t[1], t[2]), swap(t[5], t[6]), swap(t[1], t[5]);
	return t;
}
void bfs() {
	q.push(start);
	dist[start] = 0;
	while (!q.empty()) {
		string cur = q.front();
		q.pop();
		if (cur == en)return;
		string m[3];
		m[0] = move1(cur);
		m[1] = move2(cur);
		m[2] = move3(cur);
		
		for (int i = 0; i < 3; i++) {
			if (dist.count(m[i]) == 0) {
				dist[m[i]] = dist[cur] + 1;
				pre[m[i]].x = char(i + ‘A‘);
				pre[m[i]].y = cur;
				q.push(m[i]);
			}
		}
	}
}
int main() {
	for (int i = 0; i < 8; i++) {
		int x;
		cin >> x;
		start += char(x + ‘0‘);
	}
	for (int i = 0; i < 8; i++)en += char(i + ‘1‘);
	bfs();
	cout << dist[en] << endl;
	string res;
	while (en != start) {
		res += pre[en].x;
		en = pre[en].y;

	}
	reverse(res.begin(),res.end());
	cout << res << endl;
	return 0;
}

经典题：map写bfs

原文：https://www.cnblogs.com/codjjj/p/15213910.html