历届试题 九宫重排

　　如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

　　我们把第一个图的局面记为：12345678.
　　把第二个图的局面记为：123.46758
　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

思路：广搜嘛，我把  .  改成了9，然后存到了一个int里面，这样省空间

但其实用9个char来存更快，不过空间支出大一点，也没啥关系啦。

也许还有更骚的操作，请大家自行开发啦

#include<iostream>
#include<set>
#include<algorithm>
#include<queue>
#include<string>
#include<sstream>
#include<stdlib.h>

using namespace std;

int start, End, poi;

typedef struct state
{
	int start, poi, bushu;
}state;

queue<state> q;
set<int> c;

int ci[9] = { 100000000,10000000,1000000,100000,10000,1000,100,10,1 };

int swap(int start, int p1, int p2)
{
	int t1, t2;
	t1 = start / ci[p1]%10;
	start -= (t1*ci[p1]);
	t2 = start / ci[p2]%10;
	start -= (t2*ci[p2]);
	start += (t1*ci[p2]);
	start += (t2*ci[p1]);
	return start;
}

int bfs()
{
	state s = q.front();
	while (!q.empty() && s.start != End)
	{
		state temp;
		if (s.poi / 3>0)
		{
			temp.start = swap(s.start, s.poi, s.poi - 3);
			temp.poi = s.poi - 3;
			temp.bushu = s.bushu + 1;
			if (!c.count(temp.start))
			{
				q.push(temp);
				c.insert(temp.start);
			}
		}
		if (s.poi % 3 != 2)
		{
			temp.start = swap(s.start, s.poi, s.poi + 1);
			temp.poi = s.poi + 1;
			temp.bushu = s.bushu + 1;
			if (!c.count(temp.start))
			{
				q.push(temp);
				c.insert(temp.start);
			}
		}
		if (s.poi / 3<2)
		{
			temp.start = swap(s.start, s.poi, s.poi + 3);
			temp.poi = s.poi + 3;
			temp.bushu = s.bushu + 1;
			if (!c.count(temp.start))
			{
				q.push(temp);
				c.insert(temp.start);
			}
		}
		if (s.poi % 3 != 0)
		{
			temp.start = swap(s.start, s.poi, s.poi - 1);
			temp.poi = s.poi - 1;
			temp.bushu = s.bushu + 1;
			if (!c.count(temp.start))
			{
				q.push(temp);
				c.insert(temp.start);
			}
		}
		q.pop();
		s = q.front();
	}
	if (q.empty())return -1;
	return s.bushu;
}

int main()
{
	state s;
	s.bushu = 0; s.poi = poi;
	string a;
	cin >> a;
	for (int i = 0; i != 9; i++)
		if (a[i] == '.')
		{
			s.poi = i;
			a[i] = '9';
		}
	int ans = 0;
	for (int i = 0; i != a.length(); i++)
	{
		ans *= 10;
		ans += (a[i] - '0');
	}
	s.start = ans;
	cin >> a;
	for (int i = 0; i != 9; i++)
		if (a[i] == '.')a[i] = '9';
	ans = 0;
	for (int i = 0; i != a.length(); i++)
	{
		ans *= 10;
		ans += (a[i] - '0');
	}
	End = ans;
	q.push(s);
	int cnt = bfs();
	cout << cnt << endl;
	return 0;
}