题解 | #八数码#

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>;
using namespace std;
const int N = 363000;
string s = "", t = "12345678x";
int last[N];
bool vis[N];
char from[N];
map<string, int> mp;
string a[N];
int cnt = 0;
queue<int> q;
const int dir[4][2] = { 0,1,0,-1,-1,0,1,0 };
const char d[4] = { 'r','l','u','d' };

bool bfs(string s, string t)
{
	mp[s] = 1;
	cnt = 1;
	vis[1] = 1;
	a[1] = s;
	q.push(1);
	while(!q.empty())
	{
		int tmp = q.front();
		string cur = a[tmp];
		q.pop();

		int pos = cur.find('x');
		int x = pos / 3, y = pos % 3;
		for (int i = 0; i < 4; i++)
		{
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			if (dx < 0 || dy < 0 || dx >= 3 || dy >= 3) continue;
			string nxt = cur;
			swap(nxt[pos], nxt[dx * 3 + dy]);
			
			if (mp.find(nxt) != mp.end())continue;
			mp[nxt] = ++cnt;
			a[cnt] = nxt;
			vis[cnt] = 1;
			last[cnt] = tmp;
			from[cnt] = d[i];
			if (nxt == t) return 1;
			q.push(cnt);
		}
	}

	return 0;
}

void dfs(int x)
{
	if (last[x] != 0)
	{
		dfs(last[x]);
		cout << from[x];
	}
}

int main()
{
	for (int i = 1; i <= 9; i++)
	{
		char a;
		cin >> a;
		s += a;
	}
	if (bfs(s, t) == 0) cout << "unsolvable";
	else {
		dfs(mp[t]);
	}

	return 0;
}