首页 > 其他 > 详细

经典题:map写bfs

时间:2021-09-02 15:39:43      阅读:16      评论:0      收藏:0      [点我收藏+]
#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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!