HDU 1078 FatMouse and Cheese：記憶化搜索解迷宮最大奶酪

HDU 1078 FatMouse and Cheese：記憶化搜索解迷宮最大奶酪

問題描述

n×n 方格城市，每格 (p,q) 有 0~100 塊奶酪。胖鼠從 (0,0) 出發，吃掉當前格奶酪，每次可水平或垂直移動最多 k 格，且目標格奶酪數必須嚴格大於當前格。求胖鼠最多能吃多少奶酪。
輸入多組測試案例，n,k ≤ 100，以 -1 -1 結束。

樣例

輸入：
3 1
1 2 5
10 11 6
12 12 7
-1 -1
輸出：
37

分析

這是有向無環圖上的最長路徑問題：
- 狀態：位置 (x,y)。
- 轉移：從 (x,y) 向四方向走 1..k 步到 (nx,ny)，需滿足邊界內、未訪問、奶酪數嚴格增長。
- 目標：最大化路徑上奶酪總和。
普通 DFS 會重複計算子問題，導致超時。引入記憶化：`dp[x][y]` 存儲從 (x,y) 出發能獲得的最大奶酪增量（不含當前格），遞歸計算並緩存。

記憶化搜索算法

int dfs(int x, int y) {
    if (dp[x][y]) return dp[x][y]; // 已計算
    int best = 0;
    for (int step = 1; step <= k; step++) {
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d] * step;
            int ny = y + dy[d] * step;
            if (nx<0||ny<0||nx>=n||ny>=n) continue;
            if (map[nx][ny] <= map[x][y]) continue; // 嚴格遞增
            int gain = dfs(nx, ny) + map[nx][ny];
            if (gain > best) best = gain;
        }
    }
    dp[x][y] = best;
    return best;
}

主程序調用 `dfs(0,0) + map[0][0]` 即為答案。

完整代碼 (C++)

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 105;
int n, k;
int map[MAXN][MAXN];
int dp[MAXN][MAXN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int dfs(int x, int y) {
    if (dp[x][y]) return dp[x][y];
    int best = 0;
    for (int step = 1; step <= k; step++) {
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d] * step;
            int ny = y + dy[d] * step;
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (map[nx][ny] <= map[x][y]) continue;
            int gain = dfs(nx, ny) + map[nx][ny];
            if (gain > best) best = gain;
        }
    }
    dp[x][y] = best;
    return best;
}

int main() {
    while (scanf("%d%d", &n, &k) == 2) {
        if (n == -1 && k == -1) break;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &map[i][j]);
        memset(dp, 0, sizeof(dp));
        int ans = dfs(0, 0) + map[0][0];
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

• 狀態轉移方程：`dp[x][y] = max( dp[nx][ny] + map[nx][ny] )`，滿足嚴格遞增與步長限制。
• 記憶化將指數級 DFS 優化為 O(n² × k × 4) ≈ 100×100×100×4 = 4×10⁶，極快。
• 類似 POJ 1088 滑雪問題，只是多了步長 k 和四方向。