bfs_STL_简单易懂_九宫重排

用bfs搜索一下即可，用的string一维来代替二维的迷宫，用二维的char二维数组来查重我想不到，而用string只要用string的set即可；

需要注意的是搜索二维的上下左右变成一维后需要改动，注意边界：0 <= x <=8，并且在此基础上有一些特殊情况，

如x=2，若+1 == 3，在0 <= x <=8内，但却是出界的

参考代码:

#include<bits/stdc++.h>
using namespace std;
string s1, s2;
int dir[4] = {1, -1, 3, -3};
struct node{
	int x, step;
	string str;
	node() : x(), step(){}
	node(int xx, int s) : x(xx), step(s){}
};
int in(int x, int i){//判断是否出界
	if(x + i >= 0 && x + i < 9){
		if(x == 2 && i == 1 || x == 3 && i == -1 || x == 5 && i == 1 || x == 6 && i == -1){
			return 0;
		}
		return 1;
	}
	return 0;
}
void bfs(node s){
	int x, xx;
	queue<node> q;
	set<string> st;
	st.insert(s1);
	q.push(s);
	node now;
	node end;
	while(!q.empty()){
		now = q.front();
		x = now.x;
		q.pop();
		if(now.str == s2){
			cout<<now.step;
			return;
		}
		for(int i = 0; i < 4; i++){
			end = now;
			if(in(x, dir[i])){
				xx = x + dir[i];
				swap(end.str[xx], end.str[x]);
				if(!st.count(end.str)){
					end.step += 1;
					end.x = xx;
					q.push(end);
					st.insert(end.str);
				}
			}
		}
	}
}
int main(){
	cin>>s1>>s2;
	int x = s1.find(".");
	node s(x, 0);
	s.str = s1;
	bfs(s);
	return 0;
}