Giới thiệu bài toán

Bài toán được trích từ POJ 2251 và cuốn "Thông tin học Olympic", yêu cầu tìm thời gian ngắn nhất để thoát khỏi một mê cung ba chiều, hoặc xác định không thể thoát. Đây là dạng mở rộng tự nhiên của thuật toán tìm đường đi ngắn nhất trong đồ thị – sử dụng Tìm kiếm theo chiều rộng (BFS) trên không gian ba chiều.

Mô tả bài toán

Bạn đang bị mắc kẹt trong một địa ngục gồm L tầng, mỗi tầng có kích thước R × C. Mỗi ô trong không gian có thể là:

• S: vị trí bắt đầu
• E: vị trí đích đến
• .: ô trống, có thể di chuyển qua
• #: tường đá, không thể đi qua

Bạn có thể di chuyển theo 6 hướng: lên/xuống giữa các tầng, hoặc bốn hướng đông-tây-nam-bắc trong cùng một tầng. Mỗi bước mất đúng 1 phút. Không cho phép di chuyển chéo hoặc ra ngoài biên.

Yêu cầu

Với mỗi bộ dữ liệu, hãy xác định xem có thể thoát hay không. Nếu có, in ra thời gian ngắn nhất; nếu không, in ra "Trapped!".

Định dạng nhập/xuất

Dữ liệu vào:

• Nhiều bộ kiểm thử. Mỗi bộ bắt đầu bằng ba số nguyên L, R, C (1 ≤ L,R,C ≤ 100).
• Theo sau là L ma trận kích thước R×C, mô tả từng tầng.
• Các ma trận cách nhau bởi dòng trống.
• Kết thúc khi đọc 0 0 0.

Dữ liệu ra:

• Mỗi bộ kết quả in trên một dòng:
• Nếu thoát được: Escaped in X minute(s).
• Nếu không: Trapped!

Ví dụ minh họa

<strong>Input:</strong>
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

<strong>Output:</strong>
Escaped in 11 minute(s).
Trapped!

Ý tưởng giải thuật

Vì cần tìm đường đi ngắn nhất trong đồ thị vô hướng với trọng số đều bằng 1, BFS là lựa chọn tối ưu. Khác biệt ở đây là không gian tìm kiếm là ba chiều (x, y, z), do đó ta mở rộng BFS hai chiều truyền thống bằng cách thêm trục thứ ba.

Các hướng di chuyển được biểu diễn bằng ba mảng dịch chuyển:

• dx[6] = {1, -1, 0, 0, 0, 0}
• dy[6] = {0, 0, 1, -1, 0, 0}
• dz[6] = {0, 0, 0, 0, 1, -1}

Tương ứng: xuống, lên, đông, tây, trước (sang tầng cao hơn), sau (sang tầng thấp hơn).

Triển khai C++

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAX_SIZE = 105;
int levels, rows, cols;
char maze[MAX_SIZE][MAX_SIZE][MAX_SIZE];
int distanceMap[MAX_SIZE][MAX_SIZE][MAX_SIZE];

// Cấu trúc tọa độ 3D
struct Point {
    int level, row, col;
};

// 6 hướng: lên, xuống, đông, tây, trước, sau
int dl[] = {-1, 1, 0, 0, 0, 0};
int dr[] = {0, 0, -1, 1, 0, 0};
int dc[] = {0, 0, 0, 0, -1, 1};

int solve(Point start, Point end) {
    // Khởi tạo khoảng cách
    memset(distanceMap, -1, sizeof(distanceMap));
    
    queue<Point> q;
    q.push(start);
    distanceMap[start.level][start.row][start.col] = 0;
    
    while (!q.empty()) {
        Point current = q.front();
        q.pop();
        
        // Duyệt 6 hướng
        for (int i = 0; i < 6; i++) {
            int nl = current.level + dl[i];
            int nr = current.row + dr[i];
            int nc = current.col + dc[i];
            
            // Kiểm tra giới hạn
            if (nl < 0 || nl >= levels || nr < 0 || nr >= rows || nc < 0 || nc >= cols)
                continue;
                
            // Không đi vào tường
            if (maze[nl][nr][nc] == '#') continue;
            
            // Đã thăm rồi
            if (distanceMap[nl][nr][nc] != -1) continue;
            
            // Cập nhật khoảng cách
            distanceMap[nl][nr][nc] = distanceMap[current.level][current.row][current.col] + 1;
            
            // Đến đích?
            if (nl == end.level && nr == end.row && nc == end.col)
                return distanceMap[nl][nr][nc];
                
            q.push({nl, nr, nc});
        }
    }
    
    return -1; // Không thể đến đích
}

int main() {
    while (cin >> levels >> rows >> cols, levels || rows || cols) {
        Point start, finish;
        
        // Đọc dữ liệu từng tầng
        for (int l = 0; l < levels; l++) {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    cin >> maze[l][r][c];
                    if (maze[l][r][c] == 'S') {
                        start = {l, r, c};
                    } else if (maze[l][r][c] == 'E') {
                        finish = {l, r, c};
                    }
                }
            }
        }
        
        int result = solve(start, finish);
        if (result == -1) {
            cout << "Trapped!" << endl;
        } else {
            cout << "Escaped in " << result << " minute(s)." << endl;
        }
    }
    
    return 0;
}

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

• Thời gian: O(L × R × C) – mỗi ô chỉ được duyệt tối đa một lần.
• Không gian: O(L × R × C) – lưu trữ mê cung và bảng khoảng cách.

Thuật toán hiệu quả và phù hợp với giới hạn đề bài.