AcWing 845. 八数码（BFS）

题目链接

https://www.acwing.com/problem/content/description/847/

思路

这道题的难点在于怎么存储状态，因为是一个九宫格，我们其实可以把它压缩成一行，然后用字符串存储，那么这样我们就解决了状态问题，然后我们直接通过find函数或者自己手写匹配，每次找到x的位置，然后将x往四个方向移动，看是否是新状态，当然不能出界，如果我们找到了这个状态那么就返回这个状态的最短交换次数即可，如果没找到最后返回1即可，其实我是先写的DFS，然而DFS好像不太聪明的样子，然后就写了BFS，值得注意的是写BFS的时候，要么手写hash要么就用unordered_map，使用map是会超时的

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair

int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 10;
//----------------自定义部分----------------
int n,m,q;
char a[N][N];
int ans = 0x3f3f3f3f;

bool is_in(int x,int y){
	if(x >= 0 && x = 0 && y