零、題目描述

題目鏈接： LCR 130.衣櫥整理（注：LCR 130 與劍指 Offer 13 相同）

示例 1：
輸入：m = 4, n = 7, cnt = 5
輸出：18

示例 2：
輸入：m = 2, n = 3, cnt = 1
輸出：3
解釋：
滿足條件的格子坐標為 (0,0)、(0,1)、(1,0)。

• (0,0)：數位和 0+0=0 ≤ 1
• (0,1)：數位和 0+1=1 ≤ 1
• (1,0)：數位和 1+0=1 ≤ 1
• (0,2)：數位和 0+2=2 > 1（不滿足）
• (1,1)：數位和 1+1=2 > 1（不滿足）
• (1,2)：數位和 1+2=3 > 1（不滿足）

一、為什么這道題值得一看？

這道題是網格搜索問題的經典變種，核心圍繞“帶條件的路徑探索”展開，能幫你深化對深度優先搜索（DFS）在約束場景下的應用理解。

它的獨特價值在于：

1. 固定起點的探索：不同于需要遍歷多個起點的問題，本題僅從 (0,0) 出發，更聚焦于“單起點擴散”的邏輯；
2. 有限移動方向：只能向右或向下移動，需要針對性設計搜索路徑，避免無效探索；
3. 自定義過濾條件：通過數位和判斷是否訪問格子，增加了搜索過程中的“篩選”環節，考驗條件整合能力。

通過本題，你能掌握：

• 如何在 DFS 中嵌入自定義判斷條件（如數位和計算）；
• 如何處理網格中的邊界與訪問標記；
• 單起點、有限方向場景下的搜索邏輯設計。

對DFS（深度優先搜索）和洪水灌溉算法感興趣的朋友，不妨看看我的每日一題專欄。專欄里，在本篇之前的內容已經圍繞這兩個主題做了層層鋪墊——從基礎的遞歸邏輯、網格遍歷，到洪水灌溉的核心思想，每一步都有細致的拆解和代碼解析。

而今天這篇，更像是對“洪水灌溉”系列問題的一次總結收尾。因此，代碼層面不會再做過于細致的逐行講解（那些細節在前幾篇中已有充分覆蓋），重點會放在思路的梳理和這類問題的共性規律上，幫你形成完整的解題框架~

二、題目拆解：核心要素與約束

核心目標
統計從 (0,0) 出發，通過向右或向下移動可到達的、且滿足 digit(x) + digit(y) ≤ cnt 的格子總數（包含起點）。

關鍵要素解析

1. 數位和計算：
   需實現函數 digit(x)，計算數字 x 的各數位之和。例如：x=12 時，1+2=3；x=0 時，結果為 0。

2. 移動規則：
   每次移動只能選擇兩個方向：

   • 向右：(x, y) → (x, y+1)
   • 向下：(x, y) → (x+1, y)

3. 訪問條件：
   一個格子 (x, y) 可被訪問，需同時滿足：

   • 坐標在網格內：0 ≤ x < m 且 0 ≤ y < n；
   • 未被訪問過（避免重復計數）；
   • 數位和滿足：digit(x) + digit(y) ≤ cnt。

4. 計數邏輯：
   每訪問一個滿足條件的格子，就將計數器加 1，最終返回計數器的值。

三、算法實現：基于 DFS 的解決方案

完整代碼

class Solution {
public:// 方向數組：向右（0,1）、向下（1,0）int dx[2] = {0, 1};int dy[2] = {1, 0};// 標記已訪問的格子，避免重復計數bool visited[100][100] = {false};// 計數變量：記錄滿足條件的格子總數int count = 0;// 網格大小與數位和閾值（全局變量，避免參數傳遞冗余）int m, n, cnt;int wardrobeFinishing(int _m, int _n, int _cnt) {m = _m;n = _n;cnt = _cnt;// 先檢查起點是否滿足條件if (digit(0) + digit(0) > cnt) {return 0;}// 標記起點為已訪問，啟動DFSvisited[0][0] = true;dfs(0, 0);return count;}// DFS：從(x,y)出發，探索所有可達的有效格子void dfs(int x, int y) {// 訪問當前格子，計數+1count++;// 嘗試兩個方向的移動for (int i = 0; i < 2; i++) {int nx = x + dx[i];  // 新行坐標int ny = y + dy[i];  // 新列坐標// 檢查新坐標是否滿足所有條件if (isValid(nx, ny)) {visited[nx][ny] = true;  // 標記為已訪問dfs(nx, ny);             // 遞歸探索}}}// 輔助函數：判斷(nx, ny)是否可訪問bool isValid(int nx, int ny) {// 條件1：在網格邊界內if (nx < 0 || nx >= m || ny < 0 || ny >= n) {return false;}// 條件2：未被訪問過if (visited[nx][ny]) {return false;}// 條件3：數位和滿足要求if (digit(nx) + digit(ny) > cnt) {return false;}return true;}// 輔助函數：計算數字x的數位和int digit(int x) {int sum = 0;while (x > 0) {sum += x % 10;  // 累加最后一位x /= 10;        // 移除最后一位}return sum;}
};

代碼邏輯拆解

1. 方向數組設計
由于只能向右或向下移動，方向數組定義為：

• dx[0] = 0, dy[0] = 1 → 向右移動（行不變，列+1）
• dx[1] = 1, dy[1] = 0 → 向下移動（行+1，列不變）

2. 數位和計算（digit(x))

• 功能：將數字 x 拆分為各個數位，返回總和。
• 實現邏輯：通過 x % 10 取最后一位，累加至 sum，再通過 x /= 10 移除最后一位，循環至 x = 0。
• 示例：x=23 時，23%10=3，x=2；2%10=2，x=0，總和為 3+2=5。

3. 有效性判斷（isValid(nx, ny)）
整合三大條件的判斷，避免在 DFS 中重復寫邏輯：

• 邊界檢查：確保 (nx, ny) 處于網格內；
• 訪問檢查：通過 visited 數組判斷是否已訪問；
• 數位和檢查：計算 digit(nx) + digit(ny) 并與 cnt 比較。

4. DFS 遞歸流程

1. 進入 dfs(x, y) 后，先將當前格子計入總數（count++）；
2. 遍歷兩個移動方向，計算新坐標 (nx, ny)；
3. 通過 isValid(nx, ny) 檢查新坐標是否可訪問；
4. 若可訪問，標記為已訪問并遞歸調用 dfs(nx, ny)，繼續探索。

5. 起點特殊處理
在啟動 DFS 前，需先判斷起點 (0,0) 的數位和是否滿足條件。若不滿足（如 cnt < 0），直接返回 0，無需執行 DFS。

五、時間復雜度與空間復雜度

時間復雜度

• 網格訪問：每個格子最多被訪問一次，共 m×n 個格子；
• 數位和計算：對每個坐標 (x,y)，數位和計算時間為 O(log x + log y)（x 最大為 m-1，y 最大為 n-1）；
• 總復雜度：O(m×n×(log m + log n))，可簡化為 O(m×n)（因 log m 和 log n 為常數級）。

空間復雜度

• 遞歸棧：最壞情況下（所有格子均有效），遞歸深度為從 (0,0) 到 (m-1,n-1) 的路徑長度，即 O(m + n)；
• 訪問標記數組：visited 為固定大小的 100×100 數組，空間復雜度為 O(1)；
• 總復雜度：O(m + n)。

六、坑點總結

1. 數位和計算錯誤：

   • 忽略 x=0 的情況：digit(0) 應返回 0，若循環條件寫為 x >= 0 會導致死循環（x=0 時 x%10=0，x/10=0，無限循環）。
   • 錯誤處理負數：題目中 x 為坐標（非負），無需考慮負數，但需確保函數對非負整數有效。

2. 方向數組設計錯誤：
   誤加入向左或向上的方向，導致訪問無效格子或重復計數（如 (0,0) 向左移動到 (0,-1) 會越界）。

3. 未標記已訪問：
   雖然移動方向固定（右/下），理論上不會重復訪問，但特殊場景下（如 m=1, n=1）可能出錯，需嚴格標記訪問狀態。

4. 起點判斷遺漏：
   未提前檢查起點是否滿足條件，導致 (0,0) 無效時仍啟動 DFS，計數錯誤（如 cnt=-1 時，錯誤返回 1）。

七、舉一反三

掌握本題邏輯后，可嘗試解決以下類似問題：

• LeetCode 62. 不同路徑：計算從 (0,0) 到 (m-1,n-1) 的路徑總數（無過濾條件，僅統計路徑數）；
• LeetCode 63. 不同路徑 II：在 62 題基礎上增加障礙物，需在搜索中過濾障礙格子；
• 劍指 Offer 13. 機器人的運動范圍：與本題完全一致，僅表述不同。

八、洪水灌溉（Flood Fill）系列問題總結

回顧這幾天的5篇博客，從島嶼數量到今天的 衣櫥整理，我們圍繞洪水灌溉（Flood Fill）算法展開了一系列遞進式學習。這些題目雖場景各異，但核心邏輯一脈相承，又在細節上層層深入，共同構成了對網格搜索問題的完整認知。

1.共性：洪水灌溉的核心框架
所有題目都圍繞 “連通區域遍歷與標記” 展開，共享以下核心邏輯：

1. 遍歷觸發：從特定起點（或多個起點）出發，觸發深度優先搜索（DFS）或廣度優先搜索（BFS）；
2. 方向探索：通過方向數組（4方向、8方向等）遍歷相鄰單元格，模擬“洪水擴散”；
3. 訪問標記：通過原地修改（如將1改為0）或額外數組標記已訪問區域，避免重復處理；
4. 邊界控制：嚴格檢查坐標合法性（是否在網格范圍內），防止越界。

2.遞進：從基礎到進階的能力拆解

(1) 基礎：連通區域的“計數”與“計量”

• LeetCode 200. 島嶼數量：入門級題目，核心是“統計連通區域數量”。通過4方向DFS遍歷，每發現一個未標記的陸地（1）就計數，并“淹沒”整個島嶼（標記為0）。這是洪水灌溉的最基礎形態，教會我們“如何識別并標記一個完整的連通區域”。
• LeetCode 695. 島嶼的最大面積：在計數基礎上升級為“計量區域規模”。同樣用4方向DFS，但新增“面積累加”邏輯（每次訪問陸地時累加計數），并跟蹤最大值。這一步讓我們學會“在遍歷中攜帶并更新數據”。

(2)進階：思維反轉與復雜條件

• LeetCode 130. 被圍繞的區域：引入“反向標記”思維。不再直接尋找“被圍繞的區域”，而是從邊界出發標記“不被圍繞的安全區”（與邊緣連通的O），最后通過排除法處理目標區域。這一步打破了“正向搜索”的固定思維，學會“正難則反”的策略。
• LeetCode 417. 太平洋大西洋水流問題：進一步深化反向思維。通過雙標記數組（分別記錄能流向兩大洋的區域），從海洋邊界“逆流”標記可達區域，最終取交集。這題訓練了“多目標標記與結果整合”的能力。

(3)拓展：方向與條件的靈活適配

• LeetCode 529. 掃雷游戲：擴展遍歷方向至8方向（含對角線），并新增“條件終止”邏輯（根據周圍地雷數決定是否繼續擴散）。這題讓我們學會“根據場景調整探索范圍”和“動態控制遞歸深度”。
• LCR 130. 衣櫥整理：加入“自定義過濾條件”（數位和判斷），且限制移動方向為2方向（右/下）。這題展示了洪水灌溉在“帶約束的單起點擴散”場景中的應用，強調“條件過濾與方向限制”的結合。

3.收獲：從“會用”到“會變通”
通過這一系列題目，我們不僅掌握了洪水灌溉的基礎框架，更理解了“算法復用與變體適配”的核心思維：

• 不變的是框架：無論場景如何變化，“遍歷觸發→方向探索→訪問標記→邊界控制”的流程始終是核心，掌握這一點，就能應對80%的網格搜索問題；
• 可變的是細節：根據題目目標調整“起點選擇”（單起點/多起點/邊界起點）、“方向范圍”（4方向/8方向/有限方向）、“過濾條件”（無限制/數位和/高度差等）、“目標輸出”（計數/計量/標記/交集），就能將基礎框架轉化為具體問題的解法。

4.總結
洪水灌溉系列問題的本質，是 “如何系統性地探索并處理網格中的連通區域” 。從簡單的“數島嶼”到復雜的“帶條件的單起點擴散”，我們走過的每一步都是對“遍歷邏輯”“標記技巧”“思維角度”的深化。

未來遇到新的網格問題時，不妨先問自己：

• 起點在哪里？
• 需要向哪些方向擴散？
• 如何標記已訪問區域？
• 有哪些過濾條件會影響擴散？

想清楚這四個問題，再結合洪水灌溉的基礎框架，就能舉一反三，輕松應對各類變體。算法學習的核心，從來不是死記代碼，而是掌握“不變的邏輯”，并靈活調整“可變的細節”——這正是這一系列題目帶給我們的最大收獲。

歡迎在評論區分享你的解題思路或優化方案，一起碰撞思維火花～🌟

覺得有收獲的話，不妨點個贊鼓勵一下～順手關注專欄，后續還有更多算法進階內容，帶你穩步提升不迷路！😉

隨著洪水灌溉系列的收尾，接下來我們將進入DFS的記憶化搜索新專題——這是優化遞歸效率的核心技巧，能幫你解決更多“重復計算”場景的問題。下次咱們要討論的入門題是力扣 509. 斐波那契數，看似簡單的遞歸背后藏著記憶化的精妙邏輯，感興趣的朋友可以提前琢磨：如何用緩存避免重復計算？遞歸與記憶化結合能帶來多大的效率提升？蹲一波更新，帶你從基礎案例吃透記憶化搜索的本質～

這是封面原圖～謝謝支持！