Bài toán Xoay Lưới 3x3 từ Lục Cốc 2024 Quốc Gia A

Đây là giải pháp cho bài toán P10578 từ kỳ thi Lục Cốc 2024 Quốc Gia A.

Mô tả bài toán

Cho một lưới 3x3 (cửu cung), mỗi ô chứa một số khác nhau. Ở mỗi bước, chúng ta có thể chọn một khu vực 2x2 bất kỳ và xoay nó theo chiều kim đồng hồ. Ví dụ:

1 2 3
4 5 6
7 8 9

Xoay vùng góc trên bên phải sẽ cho kết quả:

1 5 2
4 6 3
7 8 9

Yêu cầu: Tìm số bước xoay tối thiểu để biến trạng thái cho trước thành:

1 2 3
4 5 6
7 8 9

Định dạng đầu vào

Dòng đầu tiên chứa số nguyên T - số lượng test case. Tiếp theo là T test case, mỗi test case gồm 3 dòng, mỗi dòng chứa 3 số biểu diễn trạng thái của lưới.

Định dạng đầu ra

Xuất T dòng, mỗi dòng chứa một số nguyên là đáp án cho test case tương ứng.

Ví dụ

Đầu vào #1

2
1 2 3
4 5 6
7 8 9
1 5 2
4 6 3
7 8 9

Đầu ra #1

0
3

Phương pháp giải pháp

Đối với bài toán này, tôi sử dụng thuật toán BFS (Tìm kiếm theo chiều rộng). Giống như khi bạn mất kính, bạn sẽ tìm kiếm xung quanh (BFS), còn nếu bạn biết bóng rơi theo hướng nào, bạn sẽ tìm kiếm theo một hướng duy nhất (DFS). Việc sử dụng DFS có thể gây ra tình trạng quá thời gian.

Tư duy giải thuật

Đầu tiên, tôi biểu diễn trạng thái lưới bằng một chuỗi 9 ký tự. Sử dụng chuỗi 1D thay vì mảng 2D giúp giảm thiểu thời gian xử lý.

Tuy nhiên, để tối ưu hơn nữa, tôi sử dụng cấu trúc dữ liệu map để lưu trữ các trạng thái đã truy cập và số bước cần thiết để đạt đến chúng.

Tôi áp dụng phương pháp ngược: bắt đầu từ trạng thái mục tiêu và thực hiện các phép quay ngược chiều kim đồng hồ để khám phá tất cả các trạng thái có thể. Cách tiếp cận này nhanh hơn so với việc bắt đầu từ trạng thái ban đầu.

Mã nguồn

#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

const string KET_QUA_MUC_TIEU = "123456789";
map<string, int> trangThaiDaTruyCap;
queue<string> hangDoi;

void BFS() {
    hangDoi.push(KET_QUA_MUC_TIEU);
    trangThaiDaTruyCap[KET_QUA_MUC_TIEU] = 1;
    
    while (!hangDoi.empty()) {
        string trangThaiHienTai = hangDoi.front();
        hangDoi.pop();
        
        string trangThaiMoi[4] = {trangThaiHienTai, trangThaiHienTai, trangThaiHienTai, trangThaiHienTai};
        
        // Xoay ngược chiều kim đồng hồ các góc
        // Góc trên trái
        trangThaiMoi[0][0] = trangThaiHienTai[1];
        trangThaiMoi[0][4] = trangThaiHienTai[3];
        trangThaiMoi[0][1] = trangThaiHienTai[4];
        trangThaiMoi[0][3] = trangThaiHienTai[0];
        
        // Góc trên phải
        trangThaiMoi[1][1] = trangThaiHienTai[2];
        trangThaiMoi[1][5] = trangThaiHienTai[4];
        trangThaiMoi[1][2] = trangThaiHienTai[5];
        trangThaiMoi[1][4] = trangThaiHienTai[1];
        
        // Góc dưới trái
        trangThaiMoi[2][3] = trangThaiHienTai[4];
        trangThaiMoi[2][6] = trangThaiHienTai[3];
        trangThaiMoi[2][4] = trangThaiHienTai[7];
        trangThaiMoi[2][7] = trangThaiHienTai[6];
        
        // Góc dưới phải
        trangThaiMoi[3][4] = trangThaiHienTai[5];
        trangThaiMoi[3][7] = trangThaiHienTai[4];
        trangThaiMoi[3][5] = trangThaiHienTai[8];
        trangThaiMoi[3][8] = trangThaiHienTai[7];
        
        // Kiểm tra các trạng thái mới
        for (int i = 0; i < 4; i++) {
            if (trangThaiDaTruyCap.find(trangThaiMoi[i]) == trangThaiDaTruyCap.end()) {
                trangThaiDaTruyCap[trangThaiMoi[i]] = trangThaiDaTruyCap[trangThaiHienTai] + 1;
                
                if (trangThaiMoi[i] == KET_QUA_MUC_TIEU) break;
                
                hangDoi.push(trangThaiMoi[i]);
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    
    BFS();
    
    while (T--) {
        string trangThaiBatDau;
        for (int i = 0; i < 9; i++) {
            char kyTu;
            cin >> kyTu;
            trangThaiBatDau += kyTu;
        }
        
        cout << trangThaiDaTruyCap[trangThaiBatDau] - 1 << endl;
    }
    
    return 0;
}

Mã nguồn sử dụng BFS để tìm đường đi ngắn nhất từ trạng thái đầu đến trạng thái mục tiêu. Các biến được đặt tên rõ ràng và có giải thích chi tiết trong comment.