#include <bits/stdc++.h>
using namespace std;
// 计算启发函数（曼哈顿距离）
int heuristic(string& state) {
int distance = 0; // 初始化曼哈顿距离总和为0
// 遍历状态字符串中的每个位置（0-8，对应3×3网格的9个格子）
for (int i = 0; i < 9; i++) {
if (state[i] == 'x') continue; // 如果是空格'x'，跳过不计算
int num = state[i] - '0'; // 将字符数字转换为整数（'1'->1, '2'->2, ...）
int target_x = (num - 1) / 3; // 计算该数字在目标状态中的行号（0,1,2）
int target_y = (num - 1) % 3; // 计算该数字在目标状态中的列号（0,1,2）
int current_x = i / 3; // 计算该数字当前位置的行号
int current_y = i % 3; // 计算该数字当前位置的列号
// 累加曼哈顿距离：行距离 + 列距离
distance += abs(target_x - current_x) + abs(target_y - current_y);
}
return distance; // 返回总曼哈顿距离作为启发值
}
int astar(string start) {
string target = "12345678x"; // 目标状态：正确排列
if (start == target) return 0; // 如果初始状态就是目标状态，直接返回0步
}
int main() {
string state; // 定义字符串变量，用于存储输入的初始状态
cin >> state; // 从标准输入读取初始状态（如"12345678x"）
cout << astar(state) << endl; // 调用A*算法求解并输出最少交换次数
return 0; // 程序正常结束
}
