HDU 1078 FatMouse and Cheese：記憶化搜索解法詳解

問題描述

FatMouse 在一個 n×n 的方格城市中藏匿了奶酪，每個格子 (p,q) 有 0 到 100 塊奶酪。老鼠從 (0,0) 出發，吃掉當前格子的奶酪後，每次只能沿水平或垂直方向跑最多 k 格，且必須跑到奶酪數量嚴格大於當前格子的位置。求老鼠被抓前能吃到的最大奶酪總量。

核心思路：記憶化深度優先搜索

這是一道經典的動態規劃問題，狀態為「從某格子出發能獲得的最大奶酪數」。由於移動方向受限於奶酪遞增，形成有向無環圖，適合用 DFS + 記憶化避免重複計算。

狀態定義

dp[x][y] 表示從格子 (x,y) 出發能吃到的最大奶酪總量（含當前格）。

轉移方程

對四個方向，步長 1 到 k，若目標格子在邊界內且奶酪更多：

dp[x][y] = max(dp[x][y], cheese[x][y] + dfs(nx, ny))

遞歸出口

若無合法移動，返回當前格奶酪數。

代碼實現要點

• 使用 dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}} 表示四方向。
• limit() 函數檢查邊界與奶酪遞增條件。
• 記憶化數組 dp 初始為 0，0 表示未計算（因奶酪數 ≥ 0，結果 ≥ 1）。
• 主程序讀入多組測試案例，以 -1 -1 結束。

複雜度分析

每個狀態最多計算一次，每狀態枚舉 4k 個轉移，總時間 O(n²k)，空間 O(n²)，滿足 n,k ≤ 100 的限制。

常見錯誤提醒

初學者易誤以為可任意走 k 步而非「恰好跑 1 到 k 步」，導致轉移邏輯錯誤；另需注意奶酪數相等時不可移動。