ZOJ 3865 Superbot：旋轉控制面板下的機器人最短路 (BFS)

問題描述

N×M 網格（≤10×10），機器人從 @ 出發，目標 $。控制面板有 4 個按鈕：左、右、上、下（初始順序），游標初指向「左」。每秒可：

1. 游標左右移（循環）。
2. 按下按鈕：機器人按游標指示方向移動一格（不可進陷阱 *）。
3. 什麼都不做。

每 P 秒面板順時針旋轉 90°（按鈕位置右移，游標位置不變）。求到達目標最短時間，不可達輸出 YouBadbad。

解題思路：狀態空間 BFS

狀態 = (x, y, cursor, time_mod_P)。但面板旋轉只影響按鈕映射，不影響游標位置。更簡潔：狀態 = (x, y, panel_orientation, cursor_pos)，其中 panel_orientation = time % 4（0..3 代表旋轉次數），cursor_pos = 0..3（游標所在面板位置）。

實際上，面板旋轉等價於「方向映射隨時間變化」。令 base_dir[4] = {左,右,上,下}。時間 t 時，面板旋轉 r = (t / P) % 4 次，實際方向 = base_dir[(cursor + r) % 4]。

狀態簡化為 (x, y, t_mod_4P)？因旋轉週期 4P 後方向映射循環。但 P ≤ 50，4P ≤ 200，狀態數 10×10×200 = 20,000 很小。直接用 time 作為 BFS 層數，狀態含 (x, y, cursor, phase) 其中 phase = (time/P)%4。

關鍵代碼片段 (C++)

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {0, 0, -1, 1};  // 左右上下 對應面板初始順序 0,1,2,3
const int dy[4] = {-1, 1, 0, 0};

struct State {
    int x, y, cursor, phase, time;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N, M, P; cin >> N >> M >> P;
        vector<string> g(N);
        for (int i = 0; i < N; ++i) cin >> g[i];
        int sx, sy, tx, ty;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j) {
                if (g[i][j] == '@') { sx=i; sy=j; }
                if (g[i][j] == '$') { tx=i; ty=j; }
            }
        // visited[x][y][cursor][phase]
        bool vis[10][10][4][4] = {};
        queue<State> q;
        q.push({sx, sy, 0, 0, 0});  // 游標初始 0(左), phase 0
        vis[sx][sy][0][0] = true;
        int ans = -1;
        while (!q.empty()) {
            State s = q.front(); q.pop();
            if (s.x == tx && s.y == ty) { ans = s.time; break; }
            int r = s.phase;  // 當前旋轉次數
            // 1. 游標左移
            int nc = (s.cursor + 3) % 4;
            int np = (s.time + 1) / P % 4;
            if (!vis[s.x][s.y][nc][np]) {
                vis[s.x][s.y][nc][np] = true;
                q.push({s.x, s.y, nc, np, s.time + 1});
            }
            // 2. 游標右移
            nc = (s.cursor + 1) % 4;
            np = (s.time + 1) / P % 4;
            if (!vis[s.x][s.y][nc][np]) {
                vis[s.x][s.y][nc][np] = true;
                q.push({s.x, s.y, nc, np, s.time + 1});
            }
            // 3. 按下按鈕
            int dir_idx = (s.cursor + r) % 4;
            int nx = s.x + dx[dir_idx], ny = s.y + dy[dir_idx];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && g[nx][ny] != '*') {
                np = (s.time + 1) / P % 4;
                if (!vis[nx][ny][s.cursor][np]) {
                    vis[nx][ny][s.cursor][np] = true;
                    q.push({nx, ny, s.cursor, np, s.time + 1});
                }
            }
            // 4. 什麼都不做
            np = (s.time + 1) / P % 4;
            if (!vis[s.x][s.y][s.cursor][np]) {
                vis[s.x][s.y][s.cursor][np] = true;
                q.push({s.x, s.y, s.cursor, np, s.time + 1});
            }
        }
        if (ans == -1) cout << "YouBadbad\n";
        else cout << ans << '\n';
    }
    return 0;
}

複雜度分析

• 狀態數 N×M×4×4 ≤ 10×10×16 = 1,600（實際 phase 只需 4，因旋轉只影響方向映射，週期 4）。
• BFS 時間 O(狀態數)，極快。

總結

ZOJ 3865 將時間依賴的方向映射編碼進 BFS 狀態。關鍵洞察：面板每 P 秒旋轉 90°，4 次旋轉回原狀，故方向映射週期為 4。狀態包含 (x, y, cursor, phase)，phase = (time/P) % 4。四種操作對應四種轉移，BFS 保證最短時間。代碼邏輯清晰，邊界條件處理完善。