Phân tích: Portal

Thách thức chính trong bài toán này là lập trình một giải pháp không có lỗi. Khá rõ ràng rằng việc giải quyết nó liên quan đến thuật toán tìm đường đi ngắn nhất. Như bạn có thể thấy, ngay cả một số người trong top 20 cũng đã bỏ qua bài này để làm các bài khác, vốn khó tìm ra ý tưởng hơn nhưng lại dễ cài đặt hơn.

Hãy cùng xem giải pháp của bmerry, vì nó rất dễ đọc và anh ấy là người chiến thắng vòng này. Sau đó, tôi sẽ tiếp tục với một số giải pháp khác hiệu quả hơn.

Một trạng thái của trò chơi tương ứng với vị trí của người chơi trong mê cung và vị trí của hai cổng, nếu chúng tồn tại. Giải pháp này coi bản đồ mê cung được đánh chỉ số từ 1, do đó các giá trị \((0, 0)\) cho tọa độ của các cổng có nghĩa là các cổng đó không tồn tại.

Tại mỗi bước, người chơi có thể tạo một cổng mới, di chuyển một bước Bắc, Nam, Đông hoặc Tây hoặc, nếu người chơi hiện đang ở gần một cổng và một cổng khác tồn tại, di chuyển từ cổng này sang cổng kia. Loại di chuyển đầu tiên có thể được thực hiện tức thời trong khi loại thứ hai và thứ ba mất một lượt.

Một bước tối ưu hóa là tìm trước, đối với mỗi ô, vị trí của các cổng có thể được tạo ra từ ô đó, vì bạn không muốn mất \(O(R + C)\) mỗi khi cần tìm các bước di chuyển có thể từ một trạng thái.

Nếu mỗi bước di chuyển đều mất đúng một lượt, thì thuật toán tìm kiếm theo chiều rộng (BFS) cổ điển có thể cung cấp cho chúng ta câu trả lời, nhưng trong đồ thị này với hai loại trọng số cho các cạnh (0 cho việc bắn cổng và 1 cho việc di chuyển), có vẻ như chúng ta cần thuật toán đường đi ngắn nhất của Dijkstra. Trên thực tế, chúng ta vẫn có thể sử dụng một thuật toán rất giống với BFS. Điểm điều chỉnh là thay vì thêm một trạng thái mới có cùng chi phí với trạng thái hiện tại vào cuối hàng đợi trạng thái, chúng ta thêm nó vào đầu hàng đợi (0-1 BFS). Bằng cách này, các trạng thái sẽ được mở rộng theo thứ tự chi phí của chúng, đây chính xác là những gì thuật toán Dijkstra thực hiện. Độ phức tạp của thuật toán này là \(O((R \times C)^3)\) thay vì \(O((R \times C)^3 \log (R \times C))\), vốn là chi phí của thuật toán Dijkstra.

Mã nguồn

Dưới đây là mã của bmerry, được sửa đổi nhẹ và thêm một số chú thích.

struct state {
    int r;
    int c;
    // portal rows
    int pr[2];
    // portal columns
    int pc[2];
};

#define ADDR(state) state.r][state.c] \
                   [state.pr[0]][state.pc[0]] \
                   [state.pr[1]][state.pc[1]

static unsigned char prio[16][16][16][16][16][16];

static const int dr[4] = {-1, 0, 1, 0};
static const int dc[4] = {0, -1, 0, 1};

int main() {
    int cases;
    cin >> cases;
    for (int cas = 0; cas < cases; cas++) {
        cin >> R >> C;
        grid.clear();
        grid.resize(R + 2);

        state start;
        memset(&start, 0, sizeof(start));
        grid[0] = string(C + 2, '#');
        grid[R + 1] = grid[0];
        for (int i = 1; i <= R; i++) {
            string line;
            cin >> line;
            grid[i] = "#" + line + "#";
            if (grid[i].find("O") != string::npos) {
                start.r = i;
                start.c = grid[i].find("O");
                grid[i][start.c] = '.';
            }
        }

        memset(prio, 255, sizeof(prio));
        prio[ADDR(start)] = 0;
        deque<state> q;
        q.push_back(start);
        int ans = -1;
        while (!q.empty()) {
            state cur = q.front();
            unsigned char pri = prio[ADDR(cur)];
            if (grid[cur.r][cur.c] == 'X') {
                ans = pri;
                break;
            }
            q.pop_front();

            for (int d = 0; d < 4; d++) {
                int hr = cur.r;
                int hc = cur.c;
                do {
                    hr += dr[d];
                    hc += dc[d];
                } while (grid[hr][hc] != '#');
                hr -= dr[d];
                hc -= dc[d];

                // adding a new portal
                for (int p = 0; p < 2; p++) {
                    state nxt = cur;
                    nxt.pr[p] = hr;
                    nxt.pc[p] = hc;
                    if (prio[ADDR(nxt)] > pri) {
                        prio[ADDR(nxt)] = pri;
                        // We push the state at the
                        // front since adding a portal
                        // is instantaneous.
                        q.push_front(nxt);
                    }
                }
            }

            for (int d = 0; d < 4; d++) {
                state nxt = cur;
                nxt.r += dr[d];
                nxt.c += dc[d];
                if (grid[nxt.r][nxt.c] != '#') {
                    if (prio[ADDR(nxt)] > pri + 1) {
                        prio[ADDR(nxt)] = pri + 1;
                        q.push_back(nxt);
                    }
                }
            }
            if (cur.pr[0] > 0 && cur.pr[1] > 0)
                for (int p = 0; p < 2; p++)
                    if (cur.pr[p] == cur.r &&
                       cur.pc[p] == cur.c) {
                        state nxt = cur;
                        nxt.r = cur.pr[1 - p];
                        nxt.c = cur.pc[1 - p];
                        if (prio[ADDR(nxt)] > pri + 1) {
                            prio[ADDR(nxt)] = pri + 1;
                            q.push_back(nxt);
                        }
                    }
        }

        printf("Case #%d: ", cas + 1);
        if (ans == -1)
            printf("THE CAKE IS A LIE\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}

Các giới hạn về dữ liệu đầu vào trong bài toán đủ nhỏ để giải pháp này vượt qua tất cả các bài kiểm tra. Có những giải pháp khác hiệu quả hơn mà chúng tôi đã nghĩ đến.

Các giải pháp khác

Việc tạo cổng bắt đầu trước khi thực sự có thể nhảy qua nó là không có ý nghĩa. Bằng cách này, chúng ta có thể cải thiện giải pháp trước đó và giảm độ phức tạp xuống \(O((R \times C)^2)\).

Như chúng ta vừa thấy, việc tạo cổng sớm là nguồn gốc của độ phức tạp, vì vậy bây giờ hãy nghĩ về cổng đích. Một khi chúng ta đã tạo một cổng đích, chúng ta cần di chuyển nhanh nhất có thể đến bức tường gần nhất, tạo một cổng bắt đầu, đi qua nó và đến đích. Vì vậy, những gì chúng ta có thể làm là chỉ giữ \(R \times C\) trạng thái và di chuyển từ trạng thái này sang trạng thái khác bằng cách đi Bắc, Tây, Nam hoặc Đông hoặc thực hiện một bước dịch chuyển tức thời (teleport) mất một vài lượt. Chúng ta có thể tính toán trong \(O(R \times C)\) thời gian mỗi bước dịch chuyển tức thời mất bao nhiêu lượt bằng cách thực hiện tìm kiếm theo chiều rộng bắt đầu từ tất cả các ô trong mê cung nơi một cổng có thể được tạo ra. Bây giờ chúng ta có thể sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất. Thuật toán cuối cùng có thể có độ phức tạp \(O(R \times C \log (R \times C))\), hoặc nếu chúng ta sử dụng thực tế là các cạnh dịch chuyển tức thời có chi phí tối đa là \(R \times C\), bằng cách sử dụng một mảng các danh sách trong thuật toán Dijkstra thay vì hàng đợi ưu tiên, chúng ta có thể giảm độ phức tạp của giải pháp xuống \(O(R \times C)\).

Thông tin thêm

• Thuật toán Dijkstra
• Tìm kiếm theo chiều rộng (BFS)

Dựa trên phân tích chính thức của Google Code Jam.