Hướng dẫn giải của Biểu diễn xiế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, hohoanghai5042011, hongthu712, lephuochauhungvuong

Hiểu bài toán

Đây là bài toán tìm đường đi ngắn nhất trong một mê cung 2D với các ràng buộc phức tạp về trạng thái. Bài toán yêu cầu tìm thời gian ngắn nhất để di chuyển từ ô S đến ô T.

Các ràng buộc quan trọng:

  1. Hướng di chuyển: Luôn di chuyển về phía trước theo hướng hiện tại (Bắc, Đông, Nam, Tây).
  2. Màu sắc: Mỗi ô vuông được chia làm 5 sector màu (1-5). Khi ở trên một ô, màu tiếp xúc với sàn nhà sẽ thay đổi khi di chuyển sang ô bên cạnh. Qui tắc chuyển màu: 1 -> 5 -> 4 -> 3 -> 2 -> 1 (hoặc suy ra cho các trường hợp còn lại).
  3. Thao tác: Mỗi lần di chuyển sang ô trống kế bên hoặc mỗi lần quay 90 độ (trái/phải) tại chỗ đều tốn 1 giây.
  4. Mục tiêu: Tìm thời gian ngắn nhất sao cho khi đến được T, màu tiếp xúc với sàn phải bằng c_T.

Đây là bài toán tìm kiếm trạng thái (State-space search) với chi phí uniform (mỗi bước tốn 1 giây), do đó thuật toán BFS (Breadth-First Search) là phù hợp nhất.

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

Cách BFS Chuẩn (Mãnh liệt)
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int dx[4] = {-1, 0, 1, 0}; // N, E, S, W
const int dy[4] = {0, 1, 0, -1};

struct State {
    int x, y, dir, color;
};

int M, N, cs, ct;
char grid[55][55];
int dist[55][55][4][6]; // x, y, direction, color (1-5)

int next_color(int c, int step) {
    // Di chuyển sang ô mới: 1->5->4->3->2->1
    // Nên ta có thể định nghĩa hàm next
    if (step == 1) { // Sang phải (theo hướng xoay) hoặc Next
       if (c == 1) return 5;
       return c - 1;
    } else { // Sang trái (Prev)
       if (c == 5) return 1;
       return c + 1;
    }
}

int main() {
    cin >> M >> N >> cs >> ct;
    int sx, sy, tx, ty;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') { sx = i; sy = j; grid[i][j] = '.'; }
            if (grid[i][j] == 'T') { tx = i; ty = j; grid[i][j] = '.'; }
        }
    }

    memset(dist, -1, sizeof(dist));
    queue<State> q;

    // Start: Facing North (0), color cs
    dist[sx][sy][0][cs] = 0;
    q.push({sx, sy, 0, cs});

    int ans = -1;

    while(!q.empty()) {
        State u = q.front(); q.pop();
        int d = dist[u.x][u.y][u.dir][u.color];

        // Check termination
        if (u.x == tx && u.y == ty && u.color == ct) {
            ans = d;
            break;
        }

        // 1. Move forward
        int nx = u.x + dx[u.dir];
        int ny = u.y + dy[u.dir];
        if (nx >= 0 && nx < M && ny >= 0 && ny < N && grid[nx][ny] != '#') {
            int nc = next_color(u.color, 1); // Logic màu khi di chuyển
            if (dist[nx][ny][u.dir][nc] == -1) {
                dist[nx][ny][u.dir][nc] = d + 1;
                q.push({nx, ny, u.dir, nc});
            }
        }

        // 2. Rotate Right (Xoay phải)
        int ndir = (u.dir + 1) % 4;
        if (dist[u.x][u.y][ndir][u.color] == -1) {
            dist[u.x][u.y][ndir][u.color] = d + 1;
            q.push({u.x, u.y, ndir, u.color});
        }

        // 3. Rotate Left (Xoay trái)
        ndir = (u.dir + 3) % 4;
        if (dist[u.x][u.y][ndir][u.color] == -1) {
            dist[u.x][u.y][ndir][u.color] = d + 1;
            q.push({u.x, u.y, ndir, u.color});
        }
    }

    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(M * N * 4 * 5)
  • Space Complexity: O(M * N * 4 * 5)

Đây là cách tiếp cận trực tiếp nhất. Ta coi mỗi trạng thái là một cặp (vị trí, hướng, màu). Sử dụng BFS để duyệt qua các trạng thái, mỗi trạng thái có 3 lựa chọn: đi thẳng, rẽ trái, rẽ phải. Ta lưu mảng dist[x][y][dir][color] để tránh duyệt lại trạng thái đã qua. Với M, N <= 50, số lượng trạng thái là 50504*5 = 50,000, hoàn toàn khả thi.

Cách BFS Tối ưu (0-1 BFS)
// Sử dụng deque thay vì queue cho 0-1 BFS
// Tuy nhiên, do mọi chi phí đều là 1 nên BFS chuẩn là tốt nhất.
// Dưới đây là tối ưu code C++ hiện đại.
#include <bits/stdc++.h>
using namespace std;

int M, N, cS, cT;
char grid[55][55];
int dist[55][55][4][6];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

struct State { int x, y, dir, color; };

int get_next_color(int c, bool forward) {
    // forward=true: di chuyển theo hướng mũi tên (tăng 1 bước logic)
    // Quy tắc: 1->5->4->3->2->1
    // Ta có thể dùng mảng hoặc công thức
    if (forward) { // Next
        if (c == 1) return 5;
        return c - 1;
    } else { // Prev
        if (c == 5) return 1;
        return c + 1;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> M >> N >> cS >> cT;
    int sx, sy, tx, ty;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') { sx = i; sy = j; grid[i][j] = '.'; }
            if (grid[i][j] == 'T') { tx = i; ty = j; grid[i][j] = '.'; }
        }
    }

    memset(dist, 0x3f, sizeof(dist));
    queue<State> q;
    dist[sx][sy][0][cS] = 0;
    q.push({sx, sy, 0, cS});

    while (!q.empty()) {
        State u = q.front(); q.pop();
        int d = dist[u.x][u.y][u.dir][u.color];

        // Terminate early if found (optional)
        if (u.x == tx && u.y == ty && u.color == cT) {
            cout << d << "\n";
            return 0;
        }

        // Move Forward
        int nx = u.x + dx[u.dir], ny = u.y + dy[u.dir];
        if (nx >= 1 && nx <= M && ny >= 1 && ny <= N && grid[nx][ny] != '#') {
            int nc = get_next_color(u.color, true);
            if (dist[nx][ny][u.dir][nc] > d + 1) {
                dist[nx][ny][u.dir][nc] = d + 1;
                q.push({nx, ny, u.dir, nc});
            }
        }

        // Rotate (Left and Right)
        for (int k = -1; k <= 1; k += 2) { // -1 (Left), 1 (Right)
            int ndir = (u.dir + k + 4) % 4;
            if (dist[u.x][u.y][ndir][u.color] > d + 1) {
                dist[u.x][u.y][ndir][u.color] = d + 1;
                q.push({u.x, u.y, ndir, u.color});
            }
        }
    }

    cout << -1 << "\n";
    return 0;
}
  • Time Complexity: O(M * N * 20)
  • Space Complexity: O(M * N * 20)

Phiên bản này chỉ khác biệt ở cách viết code gọn gàng hơn (sử dụng vector/struct, xử lý vòng lặp cho phép xoay). Logic vẫn là BFS. Do mọi thao tác đều tốn 1 đơn vị thời gian, BFS thường là đủ. Tuy nhiên, nếu có trường hợp chi phí 0 (ví dụ: xoay đổi màu không tốn thời gian), ta sẽ dùng 0-1 BFS (Dequeue). Ở đây ta giữ nguyên BFS nhưng tối ưu hóa code để dễ đọc và tránh sai sót.

Cách Thay đổi quy luật màu sắc (Reverse Logic)
// Lưu ý: Quy tắc màu 1->5->4->3->2->1
// Khi đi từ ô A sang B, màu mới = (Màu cũ - 1) % 5 (với 0 là 5)
// Hoặc có thể hiểu là đổi màu theo chu kỳ.
// Code minh họa cách xử lý màu sắc chuẩn xác

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int M, N, cS, cT;
char grid[55][55];
int dist[55][55][4][6];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

struct State { int x, y, dir, color, time; };

int main() {
    cin >> M >> N >> cS >> cT;
    int sx, sy, tx, ty;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') { sx = i; sy = j; grid[i][j] = '.'; }
            if (grid[i][j] == 'T') { tx = i; ty = j; grid[i][j] = '.'; }
        }
    }

    memset(dist, -1, sizeof(dist));
    queue<State> q;
    // Start: Facing North (0), Color cS
    dist[sx][sy][0][cS] = 0;
    q.push({sx, sy, 0, cS, 0});

    while (!q.empty()) {
        State u = q.front(); q.pop();

        if (u.x == tx && u.y == ty && u.color == cT) {
            cout << u.time << endl;
            return 0;
        }

        // 1. Move Forward
        int nx = u.x + dx[u.dir];
        int ny = u.y + dy[u.dir];
        if (nx >= 0 && nx < M && ny >= 0 && ny < N && grid[nx][ny] != '#') {
            // Logic màu: 1->5, 2->1, 3->2, 4->3, 5->4
            // Công thức: (c == 1) ? 5 : c - 1
            int nc = (u.color == 1) ? 5 : (u.color - 1);
            if (dist[nx][ny][u.dir][nc] == -1) {
                dist[nx][ny][u.dir][nc] = 1;
                q.push({nx, ny, u.dir, nc, u.time + 1});
            }
        }

        // 2. Rotate (Left/Right)
        // Left
        int ndir = (u.dir + 3) % 4;
        if (dist[u.x][u.y][ndir][u.color] == -1) {
            dist[u.x][u.y][ndir][u.color] = 1;
            q.push({u.x, u.y, ndir, u.color, u.time + 1});
        }
        // Right
        ndir = (u.dir + 1) % 4;
        if (dist[u.x][u.y][ndir][u.color] == -1) {
            dist[u.x][u.y][ndir][u.color] = 1;
            q.push({u.x, u.y, ndir, u.color, u.time + 1});
        }
    }

    cout << -1 << endl;
    return 0;
}
  • Time Complexity: O(M * N * 4 * 5)
  • Space Complexity: O(M * N * 4 * 5)

Đây là cách tiếp cận chi tiết nhất về logic màu sắc. Điểm mấu chốt là nhận ra rằng khi di chuyển sang ô bên cạnh, màu sẽ thay đổi theo một quy luật xác định (chu kỳ 5). Nếu viết sai quy luật này (ví dụ: c+1 thay vì c-1 hoặc ngược lại) sẽ sai lệch kết quả. BFS là thuật toán tối ưu ở đây.

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

Cách tiếp cận Time Space Tên
1 O(M * N * 4 * 5) O(M * N * 4 * 5) BFS Chuẩn (Mãnh liệt)
2 O(M * N * 20) O(M * N * 20) BFS Tối ưu (0-1 BFS)
3 O(M * N * 4 * 5) O(M * N * 4 * 5) Thay đổi quy luật màu sắc (Reverse Logic)

Bài học kinh nghiệm

  • State Space Search: Bài toán có thể được mô hình hóa thành đồ thị các trạng thái. Mỗi trạng thái là một cấu trúc 3-triệu-tuple (vị trí x, vị trí y, hướng nhìn, màu sắc).
  • Quy luật màu sắc: Màu sắc thay đổi theo chu kỳ 5 khi di chuyển. Nếu không nắm vững quy luật này (1->5->4->3->2->1), bài toán sẽ không giải quyết được.
  • BFS là tối ưu: Vì mọi hành động (di chuyển, xoay) đều có chi phí như nhau (1 giây), BFS đảm bảo tìm được đường đi ngắn nhất trên đồ thị các trạng thái.

Lỗi thường gặp

  • Quên kiểm tra điều kiện biên khi di chuyển (x, y < 0 hoặc >= M, N).
  • Sai quy luật chuyển màu khi di chuyển (ví dụ: lầm lẫn giữa 'tiến' và 'lùi' trong chu kỳ).
  • Quên reset lại màu sắc tại ô S và T: Ban đầu người chơi ở ô S với màu c_S, nhưng ô S có thể là vật cản hoặc trống. Trong input, ô S và T thường được đánh dấu là '.' hoặc 'S', 'T' để xử lý.
  • Lưu trữ trạng thái: Quên một chiều dữ liệu (ví dụ: chỉ lưu x, y, dir mà quên color) dẫn đến sai lầm.

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.