HDU 3152 Obstacle Course：BFS + 優先隊列求最小路徑和

問題描述

N×N 網格，每個格子有代價。從 (1,1) 走到 (N,N)，只能上下左右移動，求路徑上格子代價之和的最小值。

解題思路

經典的網格最短路問題，邊權為目標格子的代價。由於權值非負，可用 Dijkstra 算法（優先隊列優化的 BFS）。狀態：(x, y, 累積代價)。從起點開始，每次取出累積代價最小的狀態擴展四鄰域，若新累積代價更小則更新並入隊。終點第一次出隊即為最短路徑和。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 130;
const int INF = 0x3f3f3f3f;
int N, grid[MAXN][MAXN], dist[MAXN][MAXN];
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

struct Node {
    int x, y, d;
    bool operator<(const Node& o) const { return d > o.d; }
};

int dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    priority_queue pq;
    dist[1][1] = grid[1][1];
    pq.push({1, 1, grid[1][1]});
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        if (cur.d != dist[cur.x][cur.y]) continue;
        if (cur.x == N && cur.y == N) return cur.d;
        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i];
            if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
            int nd = cur.d + grid[nx][ny];
            if (nd < dist[nx][ny]) {
                dist[nx][ny] = nd;
                pq.push({nx, ny, nd});
            }
        }
    }
    return -1;
}

int main() {
    int cas = 0;
    while (cin >> N && N) {
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                cin >> grid[i][j];
        cout << "Problem " << ++cas << ": " << dijkstra() << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(N^2 log N^2) = O(N^2 log N)。
• 空間複雜度：O(N^2)。

總結

網格最短路標準模板，優先隊列實現 Dijkstra。注意起點代價包含自身，終點判斷在出隊時進行以保證最短。