---

題目

地上有一個m行n列的方格，從坐標 [0,0] 到坐標 [m-1,n-1] 。一個機器人從坐標 [0, 0] 的格子開始移動，它每次可以向左、右、上、下移動一格（不能移動到方格外），也不能進入行坐標和列坐標的數位之和大于k的格子。例如，當k為18時，機器人能夠進入方格 [35, 37] ，因為3+5+3+7=18。但它不能進入方格 [35, 38]，因為3+5+3+8=19。請問該機器人能夠到達多少個格子？

示例 1：

輸入：m = 2, n = 3, k = 1
輸出：3

示例 2：

輸入：m = 3, n = 1, k = 0
輸出：1

提示：

1 <= n,m <= 100
0 <= k <= 20

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof

---

思路

依然是典型的搜索+回溯的問題。可以選擇用DFS也可以選擇用BFS。

先講兩種方法都需要解決的問題——求數位和。

int sums(int x){int sum = 0;while(x != 0) {sum += x % 10;x /= 10;}return sum;
}

這里引入一個數位和增量公式，是我看作者：jyd的題解時學到的：

---

DFS

思路

DFS 通過遞歸，先朝一個方向搜到底（本題中應為右、下兩個方向之一），再回溯至上個節點，沿另一個方向搜索。

可行性剪枝： 在搜索中，遇到數位和超出給定值、此元素已訪問，則應立即返回。

判定元素是否被訪問通過建立一個m*n的bool數組，訪問過的位置標記為true，未訪問的位置標記為false。

• 根據可行性剪枝確定終止條件：

1. 下標越界
2. 數位和超出給定值
3. 元素已經被訪問

此時返回0，搜索結果為不可達解。

• 遞推工作：

1. 將當前節點標記為true，表示已經訪問過。
2. 從當前節點的 下、右 兩個方向開啟下層遞歸。

• 回溯返回值：
  返回 1 + 下方搜索的可達解總數 + 右方搜索的可達解總數，代表從本單元格遞歸搜索的可達解總數。

---

代碼

class Solution {int rows;int cols;bool sumnumber(int i, int j, int k){int sum = 0;while(i != 0 || j != 0){if(i != 0){sum += i % 10;i /= 10;}if(j != 0){sum += j % 10;j /= 10;}}if(sum <= k){return true;}return false;}int dfs(int i, int j, vector<vector<bool>>& vb, int& k){bool flag = sumnumber(i, j, k);if(i >= rows || j >= cols || !flag || vb[i][j]){return 0;} vb[i][j] = true;return 1 + dfs(i + 1, j, vb, k) + dfs(i, j + 1, vb, k);}
public:int movingCount(int m, int n, int k) {vector<vector<bool>> vb(m, vector<bool>(n, 0));rows = m;cols = n;return dfs(0, 0, vb, k);}
};

復雜度分析

設矩陣行列數分別為 M, N 。

• 時間復雜度 O(MN)： 最差情況下，機器人遍歷矩陣所有單元格，此時時間復雜度為 O(MN)。
• 空間復雜度 O(MN)： 最差情況下，vector<vector<bool>> vb 內存儲矩陣所有單元格的索引，使用 O(MN)的額外空間。

---

---

BFS

思路

兩者都是遍歷矩陣，但區別在于：

• DFS是向一個方向遍歷到底，再回溯，不撞南墻不回頭。
• BFS是平推的方式向前搜索。

BFS通常通過隊列來實現。

• 初始化： 將初始點 (0, 0) 加入隊列 queue ；
• 迭代終止條件： queue 為空。代表已遍歷完所有可達解。
• 迭代過程：

1. 單元格出隊： 將隊首單元格的 索引、數位和 彈出，作為當前搜索單元格。
2. 判斷是否跳過： 若
   行列索引越界
數位和超出目標值 k
當前元素已訪問過
   時，執行 continue 。
3. 標記當前單元格 ： 將單元格索引 (i, j) 存入 輔助數組 中，代表此單元格 已被訪問過 。
4. 單元格入隊： 將當前元素的 下方、右方 單元格的 索引、數位和 加入 queue 。

• 返回值： 輔助數組 的長度即為可達解的數量。

---

代碼

class Solution {bool sumnumber(int i, int j, int k){int sum = 0;while(i != 0 || j != 0){if(i != 0){sum += i % 10;i /= 10;}if(j != 0){sum += j % 10;j /= 10;}}if(sum <= k){return true;}return false;}
public:int movingCount(int m, int n, int k) {queue<pair<int,int>> que; // 臨時存儲可達解，為空則表示已經遍歷完可達解vector<vector<bool>> vb(m, vector<bool>(n, 0)); // 記錄訪問過的節點vector<int> dx = {0,1}; // 向右、下的方向數組vector<int> dy = {1,0}; // 向右、下的方向數組int res = 0; // 可達解總數que.push(make_pair(0, 0));// 等價于  //que.push({ 0, 0 });while(!que.empty()){pair<int,int> x = que.front();que.pop();int i = x.first, j = x.second;bool flag = sumnumber(i, j, k);if(i >= m || j >= n || vb[i][j] || !flag) continue;vb[i][j] = true;res++;for(int a = 0; a < 2; a++){ // 當前單元格可達int tx = i + dx[a]; int ty = j + dy[a];que.push(make_pair(tx, ty));// 將右、下方向的單元格入隊}}return res;}
};

復雜度分析

同DFS