Algorithm (BFS)

1. This problem can be converted to finding a shortest path between in a directed graph, whose node is defined by the {board_config, current_zero_position}.
2. Moreover, the graph is undirected. Thus a traditional BFS is sufficient.
3. The usual complexity is $O(|V| + |E|) = O(N^2)$. Note that we used a set keep track of the visited node, which increases an extra $\log$ factor. So in total, we have $O(N^2\log N)$.

Code

class Solution {
 public:
  int slidingPuzzle(vector<vector<int>>& board) {
    const auto R = size(board);
    const auto C = size(board[0]);
    const auto dr = array<int, 4> {1, -1, 0, 0};
    const auto dc = array<int, 4> {0, 0, 1, -1};

    struct node_t {
      vector<vector<int>> board;
      array<int, 2> zero;
    };

    const auto target = vector<vector<int>> {{1, 2, 3},
                                             {4, 5, 0}};

    auto inbound = [&](int r, int c) {
      return r >= 0 and r < R and c >= 0 and c < C;
    };

    auto walk = [&](const node_t& node, const set<vector<vector<int>>> & visited, int i) -> optional<node_t> {
      const auto [r, c] = node.zero;
      if (const auto [nr, nc] = tuple(r + dr[i], c + dc[i]); inbound(nr, nc)) {
        const auto nboard = [&](vector<vector<int>> self = {}) {
          self = node.board;
          swap(self[r][c], self[nr][nc]);
          return self;
        }();
        if (visited.find(nboard) == end(visited)) {
          return node_t{nboard, {nr, nc}};
        }
      }
      return std::nullopt;
    };

    const auto start_position = [&] {
      for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c) {
          if (board[r][c] == 0)
            return array<int, 2>{r, c};
        }
      throw std::domain_error("no starting point");
    }();

    const auto solution = [&] {
      auto visited = set<vector<vector<int>>> {};
      auto que = deque<pair<node_t, int>>{{node_t{board, start_position}, 0}};
      while (empty(que) == false) {
        const auto [cur_node, cur_dist] = que.front();
        que.pop_front();
        visited.insert(cur_node.board);
        if (cur_node.board == target)
          return cur_dist;
        for (int i = 0; i < 4; ++i) {
          if (const auto next_node = walk(cur_node, visited, i); next_node) {
            que.emplace_back(pair{next_node.value(), cur_dist + 1});
          }
        }
      }
      return -1;
    }();
    return solution;
  }