rt，我使用了一个普普通通的广搜，甚至状态我都是用 vector 套 string 做的，加了一个判重，但是交上去可以直接 A 掉。

#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <set>

using namespace std;

string s;
queue<pair<vector<string>, int>> q;
set<vector<string>> f;

pair<int, int> find(const vector<string> &v) {
  for (int i = 0; i < v.size(); i++) {
    if (v[i].find('0') != string::npos) {
      return make_pair(i, v[i].find('0'));
    }
  }
}

void record(const vector<string> &v, int second) {
  if (f.count(v)) {
    return;
  }
  q.emplace(v, second);
  f.insert(v);
}

int bfs(const vector<string> &v) {
  for (q.emplace(v, 0); q.size(); q.pop()) {
    auto [first, second] = q.front();
    if (first == vector<string>({"123", "804", "765"})) {
      return second;
    }
    pair<int, int> p = find(first);
    if (p.first > 0) {  // 往上翻
      swap(first[p.first][p.second], first[p.first - 1][p.second]);
      record(first, second + 1);
      swap(first[p.first][p.second], first[p.first - 1][p.second]);
    }
    if (p.first < 2) {  // 往下翻
      swap(first[p.first][p.second], first[p.first + 1][p.second]);
      record(first, second + 1);
      swap(first[p.first][p.second], first[p.first + 1][p.second]);
    }
    if (p.second > 0) {  // 往左翻
      swap(first[p.first][p.second], first[p.first][p.second - 1]);
      record(first, second + 1);
      swap(first[p.first][p.second], first[p.first][p.second - 1]);
    }
    if (p.second < 2) {  // 向右翻
      swap(first[p.first][p.second], first[p.first][p.second + 1]);
      record(first, second + 1);
      swap(first[p.first][p.second], first[p.first][p.second + 1]);
    }
  }
  return 114514;
}

int main() {
  cin >> s;
  cout << bfs({s.substr(0, 3), s.substr(3, 3), s.substr(6, 3)}) << '\n';
  return 0;
}