求条10pts

#include <bits/stdc++.h>
using namespace std;

string start;
string gay = "123804765";

map<string, bool> vis;

struct node {
	string a; int st;
}tmp;
queue<node> q;

void solve(node vct) {
	string s = vct.a; int stp = vct.st;
	for (int i = 0; i < 9; i ++) {
		if (s[i] == '0') {
			if (i >= 3 && i <= 8) {
				swap(s[i], s[i - 3]);
				
				if (vis[s]) {
					swap(s[i], s[i - 3]);
					continue;
				}
				vis[s] = 1;
				node t;
				t.a = s;
				t.st = stp + 1;
				q.push(t);
				swap(s[i], s[i - 3]);
			}
			if (i >= 0 && i <= 5) {
				swap(s[i], s[i + 3]);
				
				if (vis[s]) {
					swap(s[i], s[i + 3]);
					continue;
				}
				vis[s] = 1;
				node t;
				t.a = s;
				t.st = stp + 1;
				q.push(t);
				swap(s[i], s[i + 3]);
			}
			if (i % 3 == 1 || i % 3 == 2) {
				swap(s[i], s[i - 1]);
				
				if (vis[s]) {
					swap(s[i], s[i - 1]);
					continue;
				}
				vis[s] = 1;
				node t;
				t.a = s;
				t.st = stp + 1;
				q.push(t);
				swap(s[i], s[i - 1]);
			}
			if (i % 3 == 0 || i % 3 == 1) {
				swap(s[i], s[i + 1]);
				
				if (vis[s]) {
					swap(s[i], s[i + 1]);
					continue;
				}
				vis[s] = 1;
				node t;
				t.a = s;
				t.st = stp + 1;
				q.push(t);
				swap(s[i], s[i + 1]);
			}
			break;
		}
	}
	return;
}

void bfs() {
	tmp.a = start;
	tmp.st = 0;
	q.push(tmp);
	vis[start] = 1;
	while (q.size()) {
		node vct = q.front();
		q.pop();
		if (vct.a == gay) {
			cout << vct.st << '\n';
			exit(0);
		}
		solve(vct);
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> start;
	if (start == gay) {
		cout << "0\n";
		return 0;
	}
	bfs();
	return 0;
}