1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const string ed = "123804765";
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
int mdepth;
string s;
int h(string s){
int ans = 0;
for (int i = 0; i<s.size();i++){
if (s[i]=='0') continue;
int j = ed.find(s[i]);
int r = i/3, c= i%3;
int x = j/3, y = j%3;
ans+=abs(r-x)+abs(c-y);
}
return ans;
}
bool dfs(int cd, int st){
int cnt = h(s);
if (!cnt) return 1;
if (cd+cnt>mdepth) return 0;
int pos = s.find('0');
int x = pos/3, y = pos%3;
for (int i = 0;i<4;i++){
int nx = x+dx[i], ny = y+dy[i];
if (nx<0||nx>2||ny<0||ny>2||nx*3+ny==st)continue;
swap(s[pos], s[nx*3+ny]);
if(dfs(cd+1,pos)) return 1;
swap(s[pos], s[nx*3+ny]);
}
return 0;
}
void solve() {
cin >> s;
mdepth = h(s);
while(mdepth<=27&&!dfs(0,-1)) mdepth++;
cout << mdepth;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tomorin=1;
while (tomorin--) solve();
return 0;
}
|
