7542-八数码问题

宽搜离不开去重判断，所以宽搜+哈希是常用的方法。
这题棋盘为$3\times 3$，实际是一个字符串，可以这样思考，把$0$所在的位置用坐标$(x,y)$表示，而在字符串中的实际位置为：$x\ast 3+y$，注意棋盘左上角为$(0,0)$，字符串下标从$0$开始。
所以没有必要真的用二维数组来保存。
哈希表定义：

unordered_map<string,bool> mp;

其中$string$为棋盘状态，$bool$为访问标记。
队列定义：

struct node{
	string s;   //棋盘状态
	int x,y,bs; //坐标，步数
};
queue<node> q;

宽搜内部，枚举部分。

for(int i = 0; i < 4; i++){
			int tx = x.x + dx[i];
			int ty = x.y + dy[i];
			if(tx >=0 && tx <= 2 && ty >= 0 && ty <= 2){
				int a = x.x * 3 + x.y;  //计算在一维数组中的位置
				int b = tx * 3 + ty;
				string t = x.s;
				swap(t[a],t[b]);        //移动交换
				if(mp.count(t)==0){     //如果没出现个的棋盘
					mp[t] = 1;
					q.push({t,tx,ty,x.bs + 1});
				}
			}
		}