Language: C++

#include <bits/stdc++.h>
#define MAX 3
#define MAX2 9

using namespace std;

struct Puzzle{
  int f[MAX2];
  int space;
  string path;

  bool operator < (Puzzle &p){
  int i;
    for(i = 0; i < MAX2; i++){
      if( f[i] == p.f[i] ){
        continue;
      }
      return f[i] > p.f[i];
    }
    return false;
  }
};

string bfs(Puzzle);
bool isTarget(Puzzle);

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
char dir[4] = {'u', 'l', 'd', 'r'};

bool isTarget(Puzzle p){
  int i;
  for(i = 0; i < MAX2; i++){
    if( p.f[i] != (i+1) ){
      return false;
    }
  }
  return true;
}//end of isTarget func

int main(){
  Puzzle in;
  int i;
  for(i = 0; i < MAX2; i++){
    cin >> in.f[i];
    if( in.f[i] == 0 ){
      in.f[i] == MAX2;
      in.space = i;
    }
  }
  string ans = bfs(in);
  cout << ans.size() << endl;
  return 0;
}//end of main func


string bfs(Puzzle s){
  queue<Puzzle> Q;
  map<Puzzle, bool> V;
  Puzzle u,v;
  s.path = "";
  Q.push(s);
  V[s] = true;
  
  int r,tx,ty;
  int sx,sy;
  int tmp;

  while( !Q.empty() ){
    u = Q.front();
    Q.pop();
    if( isTarget(u) ){
      return u.path;
    }
    sx = u.space / MAX;
    sy = u.space % MAX;
    for(r = 0; r < 4; r++){
      tx = sx + dx[r];
      ty = sy + dy[r];
      if( tx < 0 || ty < 0 || tx >= MAX || ty >= MAX){
        continue;
      }
      v = u;
      /*swap*/
      tmp = v.f[u.space];
      v.f[u.space] = v.f[tx * MAX + ty];
      v.f[tx * MAX + ty] = tmp;

      v.space = tx * MAX + ty;
      if( !V[v] ){
        V[v] = true;
        v.path += dir[r];
        Q.push(v);
      }
    }
  }
  return "unsolvable";
}

Compiler output:
In file included from /usr/include/c++/14/string:49,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_function.h: In instantiation of 'constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Puzzle]':
/usr/include/c++/14/bits/stl_map.h:511:32:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = Puzzle; _Tp = bool; _Compare = std::less<Puzzle>; _Alloc = std::allocator<std::pair<const Puzzle, bool> >; mapped_type = bool; key_type = Puzzle]'
  511 |         if (__i == end() || key_comp()(__k, (*__i).first))
      |                             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
a.cc:63:6:   required from here
   63 |   V[s] = true;
      |      ^
/usr/include/c++/14/bits/stl_function.h:405:20: error: no match for 'operator<' (operand types are 'const Puzzle' and 'const Puzzle')
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
a.cc:12:8: note: candidate: 'bool Puzzle::operator<(Puzzle&)' (near match)
   12 |   bool operator < (Puzzle &p){
      |        ^~~~~~~~
a.cc:12:8: note:   conversion of argument 1 would be ill-formed:
a.cc:12:8: error: binding reference of type 'Puzzle&' to 'const Puzzle' discards qualifiers
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:1045:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1045 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1045:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Puzzle' is not derived from 'const std::pair<_T1, _T2>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:448:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  448 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Puzzle' is not derived from 'const std::reverse_iterator<_Iterator>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  493 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Puzzle' is not derived from 'const std::reverse_iterator<_Iterator>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1694 |     operator<(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Puzzle' is not derived from 'const std::move_iterator<_IteratorL>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1760 |     operator<(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Puzzle' is not derived from 'const std::move_iterator<_IteratorL>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~