Tóm tắt đề bài

Bài toán yêu cầu giải trò chơi xếp hình 8 số (8-puzzle) trên bảng kích thước \(3 \times 3\).

• Có 8 miếng ghép đánh số từ 1 đến 8 và một ô trống (số 0).
• Mỗi bước, ta có thể di chuyển một miếng ghép kề cạnh với ô trống vào vị trí ô trống.
• Mục tiêu: Tìm số bước di chuyển ít nhất để đưa trạng thái ban đầu về trạng thái đích:
  

  0 1 2
  3 4 5
  6 7 8
  

• Số lượng truy vấn \(T\) rất lớn (\(10^6\)), đòi hỏi xử lý cực nhanh cho mỗi testcase.

Phân tích

• Không gian trạng thái: Bảng \(3 \times 3\) có \(9! = 362,880\) hoán vị khác nhau. Đây là một con số nhỏ, hoàn toàn có thể duyệt toàn bộ không gian trạng thái.
• Tìm đường đi ngắn nhất: Vì mỗi bước di chuyển có trọng số bằng 1, thuật toán BFS (Breadth-First Search) là lựa chọn tối ưu để tìm số bước ít nhất.
• Ràng buộc về thời gian: Với \(T = 10^6\), ta không thể thực hiện BFS cho từng testcase. Thay vào đó, ta nên sử dụng kỹ thuật BFS ngược:
  • Bắt đầu BFS từ trạng thái đích.
  • Duyệt qua tất cả các trạng thái có thể đạt được và lưu lại khoảng cách (số bước) từ trạng thái đích đến trạng thái đó.
  • Với mỗi truy vấn, chỉ cần tra cứu kết quả đã tính sẵn trong bảng băm hoặc mảng.
• Biểu diễn trạng thái: Để tiết kiệm bộ nhớ và tăng tốc độ tra cứu, ta có thể nén bảng \(3 \times 3\) thành một số nguyên kiểu long long. Mỗi ô trong bảng nhận giá trị từ 0 đến 8 (cần 4 bit để biểu diễn), tổng cộng 9 ô cần \(9 \times 4 = 36\) bit.

Hướng giải quyết

1. Biểu diễn trạng thái (Bitmask)

Sử dụng một số nguyên 64-bit (long long) để lưu trữ trạng thái. Mỗi ô \((i, j)\) được lưu tại vị trí bit tương ứng:

• Ô \((i, j)\) sẽ chiếm 4 bit từ vị trí \((i \times 3 + j) \times 4\).
• Sử dụng các phép toán bit &, |, <<, >> để lấy (get) và đặt (set) giá trị tại một ô cụ thể.

2. Tiền xử lý bằng BFS

• Khởi tạo một hàng đợi \(Q\) chứa trạng thái đích 0 1 2 3 4 5 6 7 8.
• Sử dụng một std::map<long long, int> (hoặc unordered_map) để lưu khoảng cách từ trạng thái đích đến các trạng thái khác.
• Trong khi \(Q\) không trống:
  • Lấy trạng thái \(x\) ra khỏi \(Q\).
  • Tìm vị trí ô trống (số 0).
  • Thử di chuyển ô trống sang 4 hướng kề cạnh (lên, xuống, trái, phải).
  • Nếu trạng thái mới \(y\) chưa được thăm, cập nhật khoảng cách \(d[y] = d[x] + 1\) và đẩy \(y\) vào \(Q\).

3. Xử lý truy vấn

• Đọc số lượng testcase \(T\).
• Với mỗi testcase, đọc 9 số, nén chúng thành một số long long theo quy tắc đã định.
• Tra cứu trong map. Nếu trạng thái tồn tại, in ra \(d[s] - 1\) (do trong code mẫu khởi tạo \(d[\text{đích}] = 1\)). Nếu không tồn tại, in ra -1.

Độ phức tạp

• Tiền xử lý: \(O(N! \cdot \log(N!))\) với \(N=9\) nếu dùng std::map, hoặc \(O(N!)\) nếu dùng unordered_map hoặc mảng đánh dấu trực tiếp.
• Truy vấn: \(O(1)\) hoặc \(O(\log(N!))\) mỗi testcase. Với \(T=10^6\), tổng thời gian đáp ứng tốt giới hạn.
• Bộ nhớ: \(O(N!)\) để lưu trữ khoảng cách của tất cả các trạng thái.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// Các hướng di chuyển của ô trống: lên, trái, phải, xuống
const int hx[] = {-1, 0, 0, 1};
const int hy[] = {0, -1, 1, 0};

// Hàm lấy giá trị tại ô (i, j) từ số nguyên nén k
// Mỗi ô chiếm 4 bit, bảng 3x3 được trải phẳng thành 9 ô
#define get_val(k, i, j) ((k >> ((i * 3 + j) * 4)) & 15)

// Hàm đặt giá trị x vào ô (i, j) trong số nguyên nén k
void set_val(ll &k, int i, int j, int x) {
    k &= ~(15LL << ((i * 3 + j) * 4)); // Xóa 4 bit cũ
    k |= (ll(x) << ((i * 3 + j) * 4)); // Ghi 4 bit mới
}

map<ll, int> dist;

void precompute() {
    ll start_state = 0;
    // Trạng thái đích: 0 1 2 3 4 5 6 7 8
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            set_val(start_state, i, j, i * 3 + j);
        }
    }

    queue<ll> q;
    q.push(start_state);
    dist[start_state] = 1; // Dùng 1 để đánh dấu đã thăm, kết quả sẽ là dist - 1

    while (!q.empty()) {
        ll cur = q.front();
        q.pop();

        // Tìm vị trí ô trống (giá trị 0)
        int r = -1, c = -1;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (get_val(cur, i, j) == 0) {
                    r = i; c = j;
                    break;
                }
            }
        }

        // Thử di chuyển ô trống sang 4 hướng
        for (int h = 0; h < 4; ++h) {
            int nr = r + hx[h], nc = c + hy[h];
            if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3) {
                ll next_state = cur;
                int val = get_val(cur, nr, nc);

                // Hoán đổi ô trống (r, c) với ô (nr, nc)
                set_val(next_state, r, c, val);
                set_val(next_state, nr, nc, 0);

                if (dist.find(next_state) == dist.end()) {
                    dist[next_state] = dist[cur] + 1;
                    q.push(next_state);
                }
            }
        }
    }
}

int main() {
    precompute();

    int t;
    if (scanf("%d", &t) != EOF) {
        while (t--) {
            ll s = 0;
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    int a;
                    scanf("%d", &a);
                    set_val(s, i, j, a);
                }
            }
            if (dist.find(s) == dist.end()) {
                printf("-1\n");
            } else {
                printf("%d\n", dist[s] - 1);
            }
        }
    }
    return 0;
}