1from collections import deque
2
3def sliding_puzzle(board):
4    start = ''.join(str(num) for row in board for num in row)
5    target = '123450'
6    neighbors = {
7        0: [1, 3],
8        1: [0, 2, 4],
9        2: [1, 5],
10        3: [0, 4],
11        4: [3, 1, 5],
12        5: [2, 4]
13    }
14    queue = deque([(start, start.index('0'), 0)]) # (board_str, zero_index, depth)
15    visited = {start}
16    while queue:
17        board_str, zero_index, depth = queue.popleft()
18        if board_str == target:
19            return depth
20        for adj in neighbors[zero_index]:
21            new_board = list(board_str)
22            new_board[zero_index], new_board[adj] = new_board[adj], new_board[zero_index]
23            new_board_str = ''.join(new_board)
24            if new_board_str not in visited:
25                visited.add(new_board_str)
26                queue.append((new_board_str, adj, depth + 1))
27    return -1

1#include <iostream>
2#include <unordered_set>
3#include <queue>
4#include <vector>
5#include <string>
6#include <cmath>
#include <algorithm>

using namespace std;

struct Node {
    string board;
    int depth;
    int cost;
    bool operator<(const Node& other) const {
        return cost > other.cost;
    }
};

int slidingPuzzle(vector<vector<int>>& board) {
    string start;
    for (auto &row : board)
        for (auto &num : row)
            start += to_string(num);
    string target = "123450";
    vector<vector<int>> neighbor = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {3, 1, 5}, {2, 4}};
    priority_queue<Node> pq;
    unordered_set<string> visited;
    pq.push({start, 0, heuristic(start, target)});

    while (!pq.empty()) {
        Node current = pq.top(); pq.pop();
        if (current.board == target) {
            return current.depth;
        }
        visited.insert(current.board);

        int zeroIndex = current.board.find('0');
        for (int adj : neighbor[zeroIndex]) {
            string newBoard = current.board;
            swap(newBoard[zeroIndex], newBoard[adj]);
            if (visited.find(newBoard) == visited.end()) {
                pq.push({newBoard, current.depth + 1, current.depth + 1 + heuristic(newBoard, target)});
            }
        }
    }
    return -1;
}

int heuristic(const string& state, const string& goal) {
    int dist = 0;
    for (int i = 0; i < state.length(); i++) {
        if (state[i] != '0') {
            int targetPosition = goal.find(state[i]);
            dist += abs(targetPosition / 3 - i / 3) + abs(targetPosition % 3 - i % 3);
        }
    }
    return dist;
}