HDU 2757 Ocean Currents：0-1 BFS 求最小時間到達終點

問題描述

給定 n×m 網格，每個格子有海流方向（0-7 對應 8 方向）。船可順流漂移（耗時 0），或消耗 1 單位時間向任意 8 方向移動一格。求從起點到終點的最小時間。

算法選擇：0-1 BFS

邊權只有 0 和 1，優先隊列（Dijkstra）雖正確但常數大。雙端隊列 0-1 BFS 時間複雜度 O(V+E)，更優：

• 權為 0 的邊 → 推入隊頭
• 權為 1 的邊 → 推入隊尾

保證隊列中節點按距離非遞減順序，首次到達終點即為最短路。

核心代碼實現

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

struct Node { int x, y, time; };

int n, m;
int dx[8] = {-1,-1,0,1,1,1,0,-1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};
char grid[1005][1005];
bool vis[1005][1005];

bool valid(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

int bfs(Node start, Node target) {
    deque q;
    memset(vis, 0, sizeof(vis));
    start.time = 0;
    q.push_front(start);
    vis[start.x][start.y] = true;

    while (!q.empty()) {
        Node cur = q.front(); q.pop_front();
        if (cur.x == target.x && cur.y == target.y) return cur.time;

        // 1. 順流漂移（權值 0）：沿海流方向連續漂移直到邊界或已訪問
        Node nxt = cur;
        while (true) {
            int dir = grid[nxt.x][nxt.y] - '0';
            int nx = nxt.x + dx[dir];
            int ny = nxt.y + dy[dir];
            if (!valid(nx, ny) || vis[nx][ny]) break;
            nxt.x = nx; nxt.y = ny;
            nxt.time = cur.time; // 時間不增加
            if (nxt.x == target.x && nxt.y == target.y) return nxt.time;
            vis[nxt.x][nxt.y] = true;
            q.push_front(nxt); // 權值 0 入隊頭
        }

        // 2. 主動划動 8 方向（權值 1）
        for (int i = 0; i < 8; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if (!valid(nx, ny) || vis[nx][ny]) continue;
            Node move = {nx, ny, cur.time + (i == (grid[cur.x][cur.y]-'0') ? 0 : 1)};
            // 注意：若划動方向恰好等於海流方向，實際上也是順流，時間不增加
            // 但順流漂移已在上面處理，這裡只需處理非海流方向
            if (i == grid[cur.x][cur.y]-'0') continue; // 已被順流覆蓋
            move.time = cur.time + 1;
            if (move.x == target.x && move.y == target.y) return move.time;
            vis[move.x][move.y] = true;
            q.push_back(move); // 權值 1 入隊尾
        }
    }
    return -1; // 無法到達
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n >> m) {
        for (int i = 0; i < n; i++) cin >> grid[i];
        int T; cin >> T;
        while (T--) {
            Node s, t;
            cin >> s.x >> s.y >> t.x >> t.y;
            s.x--; s.y--; t.x--; t.y--; // 轉 0-based
            if (s.x == t.x && s.y == t.y) cout << 0 << '\n';
            else cout << bfs(s, t) << '\n';
        }
    }
    return 0;
}

關鍵優化點

1. 順流漂移合併：一次性將順流方向所有可達格子入隊頭，避免逐格擴展
2. 訪問標記前置：入隊即標記，防止重複入隊
3. 雙端隊列：push_front/push_back 替代優先隊列，常數極小

複雜度分析

• 每個格子最多入隊一次 → O(n×m)
• 每條邊最多鬆弛一次 → O(n×m)
• 總時間 O(n×m)，空間 O(n×m)

測試結果

原文對比：優先隊列 2000ms+，0-1 BFS 僅 500ms+，性能提升 4 倍。

總結

0-1 BFS 是處理 0/1 權圖最短路的利器，代碼簡潔、效率極高。本題關鍵在於識別「順流漂移」為 0 權邊並批量處理。