P1379 八数码难题

迭代加深做法，19分求大佬调

#include<bits/stdc++.h>
using namespace std;
string s,t;
int ok;
map<string,int> vis;
queue<string> q;         
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(string u,int cur,int lim){
	vis[u]=1;
	if(cur>lim) return;
	if(ok) return;
	if(u==t){
		printf("%d",lim);
		ok=1;
		return;
	}
	int p=u.find('0');
	int x=p/3;
	int y=p%3;
	for(int i=0;i<4;i++){
		string v=u;
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<0||nx>2||ny<0||ny>2) continue;
		int id=nx*3+ny;
		swap(v[p],v[id]);
		if(vis[v]) continue;
		dfs(v,cur+1,lim);
	}
}
int main(){
	cin>>s;
	t="123804765";
	for(int i=0;;i++){
		vis.clear();
		dfs(s,0,i);
		if(ok) break;
	}
	return 0;
}