蓝桥杯2017年第八届真题-青蛙跳杯子 （C++代码）

        暴力广搜，已经不想写哈希了，懒人 map ，虽然慢一点。 

参考代码:

#include<bits/stdc++.h>
#define Inf 0x3F3F3F3F
#define Loc freopen("baka.in", "r", stdin)
typedef long long LL;
using namespace std;

string init, aim;
map<string, bool> Vis;

void BFS() {
	queue<pair<string, int> > que; que.push(make_pair(init, 0)); Vis[init] = true;
	while (!que.empty()) {
		pair<string, int> Tmp = que.front(); Tmp.second++; que.pop();
		int Len = Tmp.first.size();
		for (int pos = 0; pos < Len; pos++)
			if (Tmp.first[pos] == '*') {
				pair<string, int> now = Tmp;
				for (int D = 1; D <= 3; D++) {
					if (pos + D >= 0 && pos + D < Len && now.first[pos + D] != '*') {
						swap(now.first[pos], now.first[pos + D]);
						if (now.first == aim) {
							cout << now.second << endl; return;
						}
						if (!Vis[now.first]) {
							Vis[now.first] = true; que.push(now);
						}
						swap(now.first[pos], now.first[pos + D]);
					}
					if (pos - D >= 0 && pos - D < Len && now.first[pos - D] != '*') {
						swap(now.first[pos], now.first[pos - D]);
						if (now.first == aim) {
							cout << now.second << endl; return;
						}
						if (!Vis[now.first]) {
							Vis[now.first] = true; que.push(now);
						}
						swap(now.first[pos], now.first[pos - D]);
					}
				}
			}
	}
}

int main() {
	cin >> init >> aim;
	BFS();
}