寒鸽儿のBlog

看到很多神仙都是一顿A* / 双向广搜 等操作。
其实状态数也没那么多

直接hash存储已经搜过的值,然后暴力地广搜就能过
用string来表示状态,map存一下就好了

#include <iostream>
#include <map>
#include <queue>
#define pis pair<int,string>

using namespace std;

const string end = "123804765";

inline int findZero(string s) { for(int i = 0; i < 9; ++i) if(s[i] == '0') return i; }
map<string, bool> hash;
queue<pis> q;
int bfs(string start) {
	hash[start] = true;
	q.push(make_pair(0, start));
	while(!q.empty()) {
		int d = q.front().first;
		string cur = q.front().second;
		q.pop();
		if(cur == end) {
			return d;
		}
		int x = findZero(cur);
		string tmp;
		if(x / 3 != 0) {
			tmp = cur;
			swap(tmp[x], tmp[x-3]);
			if(!hash[tmp]) {
				hash[tmp] = true;
				q.push(make_pair(d + 1, tmp));
			}
		}
		if(x % 3 != 0) {
			tmp = cur;
			swap(tmp[x], tmp[x - 1]);
			if(!hash[tmp]) {
				hash[tmp] = true;
				q.push(make_pair(d + 1, tmp));
			}
		}
		if(x % 3 != 2) {
			tmp = cur;
			swap(tmp[x], tmp[x + 1]);
			if(!hash[tmp]) {
				hash[tmp] = true;
				q.push(make_pair(d + 1, tmp));
			}
		}
		if(x / 3 != 2) {
			tmp = cur;
			swap(tmp[x], tmp[x + 3]);
			if(!hash[tmp]) {
				hash[tmp] = true;
				q.push(make_pair(d + 1, tmp));
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(false);
	string start;
	cin >> start;
	cout << bfs(start) << endl;
	return 0;
}