HDU 4230：最短路徑計數 (BFS + 記憶化搜索)

問題描述

給定一個網格地圖，包含起點（N/E/S/W 表示初始朝向）、終點（X）、障礙物（*）與空地。機器人每秒可執行三種操作之一：

1. 向左或向右轉向（朝向改變，位置不變），耗時 1 秒。
2. 按下按鈕，沿當前朝向前進任意步數（直到撞牆或障礙），耗時 1 秒。
3. 什麼都不做，耗時 1 秒。

求從起點到終點的最短時間，以及達成最短時間的路徑數量（模 1,000,000）。

解題思路

這是一個帶狀態的最短路問題。狀態定義為 (x, y, dir)，表示機器人位於 (x, y) 且朝向為 dir（0:北, 1:東, 2:南, 3:西）。

1. BFS 求最短步數：從起點狀態開始廣度優先搜索。轉移包括：
   • 左轉/右轉：(x, y, (dir+3)%4) 和 (x, y, (dir+1)%4)，代價 1。
   • 前進：沿 dir 方向逐步嘗試 k=1,2,... 步，直到出界或撞到 *，每個可達格子 (nx, ny, dir) 代價 1。
2. 記憶化路徑計數：在 BFS 過程中維護兩個陣列：
   • dist[x][y][dir]：到達該狀態的最短步數。
   • cnt[x][y][dir]：以最短步數到達該狀態的路徑數。
   當發現新的更短路徑時，更新 dist 並將 cnt 設為前驅狀態的計數；當發現等長路徑時，將 cnt 累加（模 1,000,000）。
3. 終止條件：BFS 結束後，檢查終點 (ex, ey) 四個朝向的 dist，取最小值 minDist，將所有等於 minDist 的 cnt 相加即為答案。

關鍵代碼片段 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 110;
const int MOD = 1000000;

struct Node { int x, y, dir, step; };

int n, m;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN][4];
int cnt[MAXN][MAXN][4];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int sx, int sy, int sdir) {
    memset(dist, 0x3f, sizeof(dist));
    memset(cnt, 0, sizeof(cnt));
    queue<Node> q;
    dist[sx][sy][sdir] = 0;
    cnt[sx][sy][sdir] = 1;
    q.push({sx, sy, sdir, 0});

    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        int x = cur.x, y = cur.y, d = cur.dir, s = cur.step;

        // 左轉
        int nd = (d + 3) % 4;
        if (s + 1 < dist[x][y][nd]) {
            dist[x][y][nd] = s + 1;
            cnt[x][y][nd] = cnt[x][y][d];
            q.push({x, y, nd, s + 1});
        } else if (s + 1 == dist[x][y][nd]) {
            cnt[x][y][nd] = (cnt[x][y][nd] + cnt[x][y][d]) % MOD;
        }

        // 右轉
        nd = (d + 1) % 4;
        if (s + 1 < dist[x][y][nd]) {
            dist[x][y][nd] = s + 1;
            cnt[x][y][nd] = cnt[x][y][d];
            q.push({x, y, nd, s + 1});
        } else if (s + 1 == dist[x][y][nd]) {
            cnt[x][y][nd] = (cnt[x][y][nd] + cnt[x][y][d]) % MOD;
        }

        // 前進 1..k 步
        for (int k = 1; ; ++k) {
            int nx = x + k * dx[d], ny = y + k * dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) break;
            if (grid[nx][ny] == '*') break;
            if (s + 1 < dist[nx][ny][d]) {
                dist[nx][ny][d] = s + 1;
                cnt[nx][ny][d] = cnt[x][y][d];
                q.push({nx, ny, d, s + 1});
            } else if (s + 1 == dist[nx][ny][d]) {
                cnt[nx][ny][d] = (cnt[nx][ny][d] + cnt[x][y][d]) % MOD;
            }
        }
    }
}

int main() {
    while (cin >> n >> m, n || m) {
        for (int i = 0; i < n; ++i) cin >> grid[i];
        int sx, sy, sdir, ex, ey;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 'N') { sx=i; sy=j; sdir=0; }
                else if (grid[i][j] == 'E') { sx=i; sy=j; sdir=1; }
                else if (grid[i][j] == 'S') { sx=i; sy=j; sdir=2; }
                else if (grid[i][j] == 'W') { sx=i; sy=j; sdir=3; }
                else if (grid[i][j] == 'X') { ex=i; ey=j; }
            }
        bfs(sx, sy, sdir);
        int minDist = INF, ways = 0;
        for (int d = 0; d < 4; ++d) {
            if (dist[ex][ey][d] < minDist) {
                minDist = dist[ex][ey][d];
                ways = cnt[ex][ey][d];
            } else if (dist[ex][ey][d] == minDist) {
                ways = (ways + cnt[ex][ey][d]) % MOD;
            }
        }
        if (minDist == INF) cout << "0 0\n";
        else cout << minDist << ' ' << ways << '\n';
    }
    return 0;
}

複雜度分析

• 狀態數：N × M × 4 ≤ 110 × 110 × 4 = 48,400。
• 每個狀態最多產生 2 個轉向 + 最多 max(N,M) 個前進狀態，總邊數 O(NM·max(N,M))。
• BFS 時間複雜度 O(NM·max(N,M))，空間 O(NM)，完全滿足限制。

總結

HDU 4230 將經典的 BFS 最短路擴展為帶方向狀態的圖搜索，並同時要求計算最短路條數。關鍵在於在 BFS 過程中同步維護 dist 與 cnt，利用「先到先得、等長累加」的原則正確統計路徑數。前進操作可一次跳多格，需仔細處理邊界與障礙物截斷。