CSES · Swap Game

§1 Đề bài tóm tắt

Cho lưới $3\times 3$ là một hoán vị của $1..9$. Mỗi bước được đổi chỗ hai ô kề ngang hoặc dọc. Cần tìm số bước nhỏ nhất để đưa lưới về dạng sắp tăng dần theo hàng. Với mẫu [[2,1,3],[7,5,9],[8,4,6]] đáp án là 4. Một test case duy nhất, không có ràng buộc input lớn.

§2 Quan sát chìa khóa

Có đúng $9! = 362{,}880$ hoán vị — đủ nhỏ để duyệt toàn bộ. Từ mỗi trạng thái sinh ra đúng 12 trạng thái kề: 6 cặp ngang (2 cặp mỗi hàng × 3 hàng) cộng 6 cặp dọc. Mọi swap đều có chi phí bằng $1$, nên bài toán quy về đường đi ngắn nhất trên đồ thị unit-weight — đúng định nghĩa của BFS. Không cần Dijkstra, không cần A*, không cần heuristic.

Cho người mới

§3 Tiếp cận ngây thơ

Phản xạ đầu tiên là brute force theo chuỗi swap: thử mọi dãy swap có thể, chọn dãy ngắn nhất. Mỗi bước có 12 lựa chọn nên sau $k$ bước có $12^k$ dãy — bùng nổ ngay khi $k \ge 8$.

Phản xạ thứ hai là greedy: mỗi bước chọn swap đưa nhiều ô về đúng vị trí nhất. Cách này sai vì đôi khi phải "lùi 1 bước để tiến 2 bước" — đẩy 1 ô sai sang chỗ khác để mở đường cho ô khác. Cả hai cách đều không kiểm soát được việc lặp lại trạng thái cũ — đó là điều BFS giải quyết bằng visited.

Cho người mới

§4 Ý tưởng thuật toán

Hãy đổi cách nhìn. Đừng nghĩ "tôi đang sắp xếp 1 mảng" — hãy nghĩ "tôi đang đi trên 1 bản đồ khổng lồ". Mỗi cách bày lưới $3\times 3$ là 1 thành phố trên bản đồ. Hai thành phố nối với nhau bằng 1 con đường dài 1 km nếu bạn có thể biến thành phố này thành thành phố kia chỉ bằng đúng 1 swap kề. Câu hỏi gốc trở thành: từ thành phố start đến thành phố target ($[1..9]$), con đường ngắn nhất dài bao nhiêu km?

Khi mọi con đường có cùng độ dài, có 1 thuật toán đặc biệt làm việc này hoàn hảo: BFS (Breadth-First Search). BFS đi theo từng lớp: lớp 0 là start, lớp 1 là 12 thành phố cách start đúng 1 swap, lớp 2 là tất cả thành phố cách start đúng 2 swap (chưa thuộc lớp 0 hoặc 1), v.v. Lần đầu BFS chạm đến target ở lớp $k$, ta biết ngay đáp án là $k$ — không cần đi tiếp.

Tổng số thành phố là $9!$ — chỉ khoảng 360 nghìn — và mỗi thành phố sinh đúng 12 hàng xóm, nên toàn bộ duyệt vừa vặn trong vài chục mili giây. Mẹo còn lại là mã hóa mỗi lưới thành 1 số nguyên (ví dụ 1 số base-9 chín chữ số) để dùng làm key của mảng visited, tránh dùng map<string,int> chậm.

Cho người mới

§5 Hình dung — BFS chạy thật

Widget bên dưới minh họa BFS trên 1 đồ thị 5-node để bạn thấy queue, visited, và current node thay đổi qua từng bước. Đặc biệt chú ý step 6: lúc thuật toán cố push 1 node đã trong visited — đó chính là khoảnh khắc visited cứu BFS khỏi vòng lặp vô tận.

Cho người mới

§6 Vì sao BFS đúng

Tính đúng đắn dựa trên 1 bất biến lớp: khi pop 1 node ra khỏi queue, dist của nó đã là khoảng cách ngắn nhất. Quy nạp theo lớp $k$. Cơ sở: lớp 0 chỉ chứa start với dist = 0.

Bước quy nạp: giả sử mọi node ở lớp $\le k$ đã được pop với dist đúng. Xét node $u$ thuộc lớp $k+1$ khi pop. Nếu tồn tại đường đi ngắn hơn $k+1$ tới $u$, đường đó phải đi qua 1 node $v$ ở lớp $\le k$ — nhưng khi xử lý $v$, $u$ đã được mark visited với dist = k+1, mâu thuẫn. Vì cạnh có trọng số $1$, lớp $k+1$ chính là tập các láng giềng chưa visited của lớp $k$. ∎

§7 Cài đặt

  1. Mã hóa trạng thái. Đọc lưới row-major thành dãy 9 chữ số, ép thành số nguyên base-9 (max $\approx 387 \cdot 10^6$).
  2. Pre-compute 12 cặp kề. Mảng pairs[12][2]: 6 cặp ngang $\{(0,1),(1,2),(3,4),(4,5),(6,7),(7,8)\}$ + 6 cặp dọc $\{(0,3),(3,6),(1,4),(4,7),(2,5),(5,8)\}$.
  3. Init. Tính start_code và target_code $= 012345678_9$. Push (start, 0), mark visited[start] = true.
  4. Vòng BFS. Pop (u, d). Với mỗi cặp: swap, encode lại thành $v$. Nếu $v$ = target → return $d+1$. Nếu chưa visited → mark + push $(v, d+1)$.
  5. Edge case. Lưới đã sắp xếp sẵn → return 0. Mảng visited size $9^9$ nên cấp phát ngoài main.

§8 Code C++

Block 1 — Encode/decode + swap helper. Biến mỗi lưới thành 1 khóa nguyên duy nhất.

int powers[10];
int swap_at(int grid, int i, int j) {
    int a = grid % powers[i+1] / powers[i];
    int b = grid % powers[j+1] / powers[j];
    return grid - a*powers[i] - b*powers[j]
                + b*powers[i] + a*powers[j];
}

Block 2 — Tiền xử lý. Tính powers[], target, đọc input grid.

powers[0] = 1;
for (int i = 1; i < 10; i++) powers[i] = 9 * powers[i-1];
vector<bool> vis(powers[9], false);

int target = 0;
for (int i = 8; i >= 0; i--) target += (8-i) * powers[i];

int grid = 0, num;
for (int i = 8; i >= 0; i--) {
    cin >> num;
    grid += (num-1) * powers[i];
}

Block 3 — BFS loop. Đây là động cơ shortest path. Sinh 12 neighbor mỗi pop.

queue<pair<int,int>> q;
q.push({grid, 0});
vis[grid] = true;
while (!q.empty()) {
    auto [g, dist] = q.front(); q.pop();
    if (g == target) { cout << dist; return 0; }

    for (int i = 0; i < 8; i++) {            // 6 swap ngang
        if (i % 3 == 2) continue;
        int g2 = swap_at(g, 8-i, 8-(i+1));
        if (!vis[g2]) { vis[g2] = true; q.push({g2, dist+1}); }
    }
    for (int i = 0; i < 6; i++) {            // 6 swap dọc
        int g2 = swap_at(g, 8-i, 8-(i+3));
        if (!vis[g2]) { vis[g2] = true; q.push({g2, dist+1}); }
    }
}

§9 Độ phức tạp

Time: $O(9! \cdot 12) \approx 4.4 \times 10^6$ — mỗi state vào queue đúng 1 lần và sinh 12 neighbor. Space: $O(9^9)$ bool cho visited ($\approx 48$ MB nếu dùng bitset hoặc index base-9).

§10 Bẫy thường gặp

  • Mark visited lúc pop thay vì lúc push. Cùng 1 state bị push nhiều lần, queue phình $10\times$, có thể MLE.
  • Sinh sai 12 cặp kề. Quên loại cặp $(2,3)$ — kề trong mảng phẳng nhưng không kề trên lưới (cuối hàng 1, đầu hàng 2).
  • Encode ngược row/column. Đọc row-major nhưng so sánh column-major → sai đáp án mà không crash.
  • Dùng map<string,int> thay vì mảng nguyên → chậm hơn $10\times$ vì hash + so sánh chuỗi.
  • Quên check target ngay sau pop. Nếu chỉ check khi sinh neighbor, sẽ bỏ sót trường hợp lưới đã sắp sẵn.