[题记-BFS]九宫重排——蓝桥杯

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

我们把第一个图的局面记为：12345678. 把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
——
输入：输入第一行包含九宫的初态，第二行包含九宫的终态。
输出：输出最少的步数，如果不存在方案，则输出-1。
——
样例：
13524678.
46758123.
输出：22
————————————————————————————————————————
思路：
将每一种图看做一个状态，每次都是将 “ . ”的位置进行移动从而更新状态。用BFS宽搜即可。
★：我没有创建二维数组，而是用一个字符串来保存每一个状态，需要注意：在2，3或5，6位置，是不能够更新状态的。

#include <iostream>
#include <queue>
#include <map>
using namespace std;

typedef struct node {
	string s;
	int step;
}node;
map<string,int> m;//记录状态 
queue<node> v;//队列 

int dir[4] = {1,-1,3,-3};//方向数组 
string end_s;//最终状态 

//不能更新的状态 
bool check( int x, int lx ) {
	if( x == 2&& lx == 3 ) return false;
	if( x == 3&& lx == 2 ) return false;
	if( x == 5&& lx == 6 ) return false;
	if( x == 6&& lx == 5 ) return false;
	return true;
}

int main() {
	
	node head;//队头 
	cin >> head.s >> end_s;
	
	head.step = 0;
	m[head.s] = 1;
	
	//判断队头是不是最终状态 
	if( head.s == end_s ) {
		cout << 0;
		exit(0);
	} 
	
	v.push(head);//入队 
	
	while( v.size() ) {
		node now = v.front();
		
		for( int i = 0; i < 4; i++ ) {
			
			//寻找 . 的位置和要更新的位置 
			int x = now.s.find('.');
			int lx = x + dir[i];
			
			//判断状态是够可行 
			if( lx < 0|| lx > 8 ) continue;
			if( !check(x, lx) ) continue;
			
			node l;
			l.step = now.step + 1;
			l.s = now.s;
			swap(l.s[lx], l.s[x]);
			
			//判断状态是否已经遇到过 
			if( m[l.s] ) continue;
			else m[l.s] = 1;
			
			if( l.s == end_s ) {
				cout << l.step;
				exit(0);
			}
			v.push(l);
		}
		
		v.pop();
	}
	
	cout << -1;
	
	return 0;
}