Hướng dẫn giải của Lăn xúc sắc


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, FlashNealMoon, thichluyencode, user00000

Hiểu bài toán

Bài toán yêu cầu tìm chi phí nhỏ nhất để di chuyển một con xúc xắc từ ô bắt đầu đến ô kết thúc trên một lưới M x N. Con xúc xắc có thể lăn sang trái, phải, tiến, lùi. Chi phí cho mỗi lần lăn được tính bằng số ghi trên ô mới nhân với số trên mặt của xúc xắc tiếp xúc với mặt bàn sau khi lăn. Ban đầu, mặt trước là 1, mặt trên là 2, mặt phải là 3. Các mặt đối diện tổng bằng 7. Bài toán này là tìm đường đi có chi phí nhỏ nhất trong một đồ thị có trạng thái phức tạp (bao gồm vị trí và trạng thái quay của xúc xắc).

Các cách tiếp cận

Cách Dijkstra
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
const int INF = 1e9;

int M, N;
int grid[N][N];
int dist[N][N][7][7]; // dist[r][c][front][top]: chi phí nhỏ nhất đến (r, c) với mặt trước là front và mặt trên là top

struct State {
    int r, c;
    int front, top, right;
    int cost;
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

// Hàm cập nhật trạng thái xúc xắc sau khi lăn
// new_front, new_top, new_right được tính dựa trên hướng lăn
void roll(int dir, int f, int t, int r, int &nf, int &nt, int &nr) {
    nf = f; nt = t; nr = r;
    // 0: Lùi (Back), 1: Tiến (Front), 2: Trái (Left), 3: Phải (Right)
    // Tên hướng trong bài là Left, Right, Front, Back
    // Giả sử: 0: Lùi (lenh tang r), 1: Tiến (giam r), 2: Trái (giam c), 3: Phải (tang c)
    // Logic lăn:
    // Lùi (Back): new_top = 7 - new_front (old front), new_front = old bottom (7 - old top)
    // Tiến (Front): new_top = old front, new_front = old top
    // Trái (Left): new_top = old right, new_right = old top
    // Phải (Right): new_top = old left, new_left = old top
    // Ta cần tracking front, top, right tuong duong 3 mat doc lap.
    // Khoi tao: front=1, top=2, right=3. Math opposite = 7.
    // Left = 7 - right, Bottom = 7 - top, Back = 7 - front.

    int bottom = 7 - t;
    int left = 7 - r;
    int back = 7 - f;

    if (dir == 0) { // Lùi (tang hang)
        nf = t;
        nt = back;
        nr = r; // Phai va Trai khong doi
    } else if (dir == 1) { // Tiến (giam hang)
        nf = bottom;
        nt = f;
        nr = r;
    } else if (dir == 2) { // Trái (giam cot)
        nf = r;
        nt = f;
        nr = bottom;
    } else if (dir == 3) { // Phải (tang cot)
        nf = left;
        nt = f;
        nr = top;
    }
}

int solve() {
    int startR, startC, endR, endC;
    cin >> startR >> startC >> endR >> endC;
    // Chinh sua input theo code cu: input la (row, col) va duyet tu 1
    // Trong code duoi day, minh su dung chi so tu 0

    // Reset dist
    for(int i=0; i<M; ++i)
        for(int j=0; j<N; ++j)
            for(int f=1; f<=6; ++f)
                for(int t=1; t<=6; ++t)
                    dist[i][j][f][t] = INF;

    priority_queue<State, vector<State>, greater<State>> pq;

    // Trang thai bat dau
    // Kiem tra input: '2 2 3 3' co nghia la bat dau o (2,2) ket thuc o (3,3)
    // Neu input duoc doc vao la M, N, grid, r1, c1, r2, c2
    // Va toa do bat dau la (startR, startC).
    // Trang thai dau: front=1, top=2, right=3
    // Chi phí ban đầu là 0, nhưng chi phí tính khi lăn. 
    // Chi phí tại ô hiện tại (nếu k lăn) không được tính.
    // Tuy nhiên, thường bài này chi phí tính khi lăn TOI ô mới.
    // Lev 1: Chi phí tại ô bắt đầu = 0.

    // Để an toàn, Dijkstra từ start.
    // Lưu ý: Input trong code mẫu có thể 1-based index. Ta sẽ convert về 0-based.

    // Code mẫu từ các solution:
    // Input: M N, grid, r1 c1 r2 c2
    // Ví dụ: 2 2 3 3 -> start (2,2), end (3,3)

    // Logic Dijkstra:
    // Pop state: (r, c, f, t, right, cost)
    // Neu (r, c) == end, return cost.
    // Thu 4 huong.
    // Tinh chi phí mới = cost + grid[new_r][new_c] * bottom_of_new_state.
    // Neu < dist[new_r][new_c][new_f][new_t], update.

    // Khoi tao:
    // O bat dau, chua lăn. Neu o bat dau cung la o ket thuc, chi phi la 0.
    // Tuy nhien, de quy uoc chung, ta bat dau tu o start, chi phi 0.
    // Khi lân lan dau tien, chi phi se duoc tinh.

    // Sua lai logic: Dist luu chi phí để ĐẾN trạng thái đó.
    // O bat dau co dist = 0.
    // Khi lăn sang ô mới, cost moi = dist_hientai + (so tren o moi) * (mat duoi cua xuc sac moi).

    // Khoi tao:
    dist[startR-1][startC-1][1][2] = 0;
    pq.push({startR-1, startC-1, 1, 2, 3, 0});
    // Note: mat duoi ban dau la 5 (7-2). Mat trai la 4 (7-3). Mat sau la 6 (7-1).

    int dr[] = {-1, 1, 0, 0}; // Lên, Xuống, Trái, Phải (theo trục hàng, cột)
    int dc[] = {0, 0, -1, 1};
    // Mapping huong lăn:
    // 0: Lên (Back) -> tang hang (index 0 cua dr la -1 hang -> len)
    // 1: Xuống (Front) -> giam hang
    // 2: Trái (Left)
    // 3: Phải (Right)
    // Huong lăn trong bai: Left, Right, Front, Back.
    // Trong code minh se map lai cho de quan ly.
    // 0: Back (Len) -> new_r = r - 1
    // 1: Front (Xuong) -> new_r = r + 1
    // 2: Left (Trai) -> new_c = c - 1
    // 3: Right (Phai) -> new_c = c + 1

    while(!pq.empty()) {
        State u = pq.top(); pq.pop();

        if(u.cost != dist[u.r][u.c][u.front][u.top]) continue;

        if(u.r == endR-1 && u.c == endC-1) return u.cost;

        for(int dir = 0; dir < 4; ++dir) {
            int nr = u.r, nc = u.c;
            if(dir == 0) nr--; // Len
            else if(dir == 1) nr++; // Xuong
            else if(dir == 2) nc--; // Trai
            else if(dir == 3) nc++; // Phai

            if(nr < 0 || nr >= M || nc < 0 || nc >= N) continue;

            int nf, nt, nr_side;
            roll(dir, u.front, u.top, u.right, nf, nt, nr_side);

            // Tinh mat duoi cua trang thai moi
            int bottom = 7 - nt;
            int add_cost = grid[nr][nc] * bottom;

            if(dist[nr][nc][nf][nt] > u.cost + add_cost) {
                dist[nr][nc][nf][nt] = u.cost + add_cost;
                pq.push({nr, nc, nf, nt, nr_side, dist[nr][nc][nf][nt]});
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if(cin >> M >> N) {
        for(int i=0; i<M; ++i)
            for(int j=0; j<N; ++j)
                cin >> grid[i][j];
        cout << solve() << endl;
    }
    return 0;
}
  • Time Complexity: O(M * N * 6 * 6 * log(M * N * 6 * 6))
  • Space Complexity: O(M * N * 6 * 6)

Sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất. Trạng thái của đồ thị bao gồm tọa độ (hàng, cột) và trạng thái của xúc xắc (mặt trên, mặt trước). Để giảm số lượng trạng thái, ta có thể chỉ cần lưu mặt trên và mặt trước (hoặc mặt trên và mặt phải) vì các mặt còn lại có thể suy ra. Sử dụng priority queue để ưu tiên các trạng thái có chi phí thấp nhất. Độ phức tạp là O(MN36log(MN*36)) do có最多 36 trạng thái xúc xắc tại mỗi ô.

Cách BFS với Chi phí (Dijkstra)
// Giải pháp tham khảo từ user FlashNealMoon
#include <bits/stdc++.h>
using namespace std;
#define nmax 101
#define oo 1000000001
int n, m, f[nmax][nmax][7][7][7], b[nmax][nmax];
int xs, ys, xe, ye;
struct label {
    int x, y, fro, top, right;
    int val;
};
struct cmp {
    bool operator()(label &a, label &b) { return a.val > b.val; } // Min Heap
};

void enter() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> b[i][j];
    cin >> xs >> ys >> xe >> ye;
}

label W(label u) { // Di chuyển lui (Back) - tang hang
    label v;
    v.x = u.x + 1; v.y = u.y;
    v.fro = u.top; v.top = 7 - u.fro; v.right = u.right;
    v.val = u.val + b[v.x][v.y] * (7 - v.top); // Chi phí = số ô * mặt dưới (7 - top)
    return v;
}

label S(label u) { // Di chuyển tới (Front) - giam hang
    label v;
    v.x = u.x - 1; v.y = u.y;
    v.fro = 7 - u.top; v.top = u.fro; v.right = u.right;
    v.val = u.val + b[v.x][v.y] * (7 - v.top);
    return v;
}

label A(label u) { // Di chuyển trái (Left) - giam cot
    label v;
    v.x = u.x; v.y = u.y - 1;
    v.fro = u.right; v.top = u.top; v.right = 7 - u.fro;
    v.val = u.val + b[v.x][v.y] * (7 - v.top);
    return v;
}

label D(label u) { // Di chuyển phải (Right) - tang cot
    label v;
    v.x = u.x; v.y = u.y + 1;
    v.fro = 7 - u.right; v.top = u.top; v.right = u.fro;
    v.val = u.val + b[v.x][v.y] * (7 - v.top);
    return v;
}

void solve() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= 6; k++)
                for (int l = 1; l <= 6; l++)
                    for (int r = 1; r <= 6; r++)
                        f[i][j][k][l][r] = oo;

    label start;
    start.x = xs; start.y = ys;
    start.fro = 1; start.top = 2; start.right = 3;
    start.val = 0;

    priority_queue<label, vector<label>, cmp> pq;
    f[xs][ys][1][2][3] = 0;
    pq.push(start);

    while (!pq.empty()) {
        label u = pq.top(); pq.pop();
        if (u.val != f[u.x][u.y][u.fro][u.top][u.right]) continue;
        if (u.x == xe && u.y == ye) {
            cout << u.val;
            return;
        }

        label v;
        // Check 4 huong
        if (u.x < n) { // Di ve phia sau (W)
            v = W(u);
            if (v.val < f[v.x][v.y][v.fro][v.top][v.right]) {
                f[v.x][v.y][v.fro][v.top][v.right] = v.val;
                pq.push(v);
            }
        }
        if (u.x > 1) { // Di ve phia truoc (S)
            v = S(u);
            if (v.val < f[v.x][v.y][v.fro][v.top][v.right]) {
                f[v.x][v.y][v.fro][v.top][v.right] = v.val;
                pq.push(v);
            }
        }
        if (u.y > 1) { // Di ve phia trai (A)
            v = A(u);
            if (v.val < f[v.x][v.y][v.fro][v.top][v.right]) {
                f[v.x][v.y][v.fro][v.top][v.right] = v.val;
                pq.push(v);
            }
        }
        if (u.y < m) { // Di ve phia phai (D)
            v = D(u);
            if (v.val < f[v.x][v.y][v.fro][v.top][v.right]) {
                f[v.x][v.y][v.fro][v.top][v.right] = v.val;
                pq.push(v);
            }
        }
    }
    cout << -1;
}

int main() {
    enter();
    solve();
    return 0;
}
  • Time Complexity: O(M * N * 6 * 6 * 6 * log(M * N * 6 * 6 * 6))
  • Space Complexity: O(M * N * 6 * 6 * 6)

Đây là cách cài đặt trực quan nhất của Dijkstra. Trạng thái lưu cả 3 chiều (front, top, right) thay vì chỉ 2. Điều này làm tăng không gian và độ phức tạp một chút (từ 36 lên 216 trạng thái ở mỗi ô) nhưng logic cập nhật hướng dễ hiểu hơn. Các hàm W, S, A, D mô phỏng chính xác cách chuyển động của xúc xắc.

Cách BFS Chuẩn ( không dùng chi phí)
// Không khả thi cho bài toán này do chi phí thay đổi theo đường đi
  • Time Complexity: N/A
  • Space Complexity: N/A

BFS thông thường chỉ tìm đường đi ngắn nhất về số bước đi (số lần lăn). Tuy nhiên, chi phí phụ thuộc vào tổng số ghi trên các ô và số trên mặt xúc xắc tại thời điểm đó. Ví dụ, đi qua một ô giá trị cao khi mặt trên là 1 sẽ rẻ hơn đi qua đó khi mặt trên là 6. Do đó, BFS không đảm bảo tìm được chi phí tối ưu. Đây là một dạng sai lầm thường gặp khi chuyển từ bài toán tìm đường đi đơn giản sang bài toán có trọng số.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(M * N * 6 * 6 * log(M * N * 6 * 6)) O(M * N * 6 * 6) Dijkstra
2 O(M * N * 6 * 6 * 6 * log(M * N * 6 * 6 * 6)) O(M * N * 6 * 6 * 6) BFS với Chi phí (Dijkstra)
3 N/A N/A BFS Chuẩn ( không dùng chi phí)

Bài học kinh nghiệm

  • Bài toán có thể mô hình hóa thành tìm đường đi ngắn nhất trên đồ thị với trạng thái là (vị trí, hướng của xúc xắc).
  • Chỉ cần lưu 2 mặt (ví dụ: Front và Top) là đủ để xác định trạng thái vì Face Right, Left, Bottom, Back có thể suy ra.
  • Thuật toán Dijkstra là bắt buộc vì chi phí di chuyển không đều (phụ thuộc vào giá trị ô và hướng xúc xắc).

Lỗi thường gặp

  • Sai lệch trong việc tính toán các mặt đối diện (ví dụ: mặt dưới = 7 - mặt trên).
  • Lầm tưởng rằng BFS (vì số bước) sẽ cho ra chi phí tối ưu.
  • Quên kiểm tra biên khi lăn xúc xắc ra khỏi lưới.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.