1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int SlidingPuzzle(int[][] board) {
6        string start = string.Join("", board[0]) + string.Join("", board[1]);
7        string target = "123450";
8        int[][] neighbors = {
9            new int[] {1, 3},
10            new int[] {0, 2, 4},
11            new int[] {1, 5},
12            new int[] {0, 4},
13            new int[] {3, 1, 5},
14            new int[] {2, 4}
15        };
16        Queue<(string, int)> queue = new Queue<(string, int)>();
17        queue.Enqueue((start, 0));
18        HashSet<string> visited = new HashSet<string> { start };
19        while (queue.Count > 0) {
20            (string status, int steps) = queue.Dequeue();
21            if (status == target) return steps;
22            int zeroIndex = status.IndexOf('0');
23            foreach (int adj in neighbors[zeroIndex]) {
24                char[] newStatus = status.ToCharArray();
25                (newStatus[zeroIndex], newStatus[adj]) = (newStatus[adj], newStatus[zeroIndex]);
26                string newBoard = new string(newStatus);
27                if (!visited.Contains(newBoard)) {
28                    visited.Add(newBoard);
29                    queue.Enqueue((newBoard, steps + 1));
30                }
31            }
32        }
33        return -1;
34    }
35}

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;
}