求调代码,使用迭代加深法完成此题,但只能通过4个点,其余全部超时。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const long long MAXN = 10005;
string s, t;
int ok;
map<string, int> vis;
queue<string> q;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
void dfs(string u, int cur, int lim){
if(cur > lim) return ;
if(ok) return ;
if(u == t){
cout << lim << '\n';
ok = 1;
return ;
}
int p = u.find('0');
int x = p / 3;
int y = p % 3;
for(ll i = 0; i < 4; i++){
string v = u;
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx > 2 || ny > 2) continue;
int id = nx * 3 + ny;
swap(v[p], v[id]);
dfs(v, cur + 1, lim);
}
}
signed main(){
cin >> s;
t = "123804765";
for(ll i = 0; ; i++){
dfs(s, 0, i);
if(ok) break;
}
return 0;
}