?劍指 Offer 13. 機器人的運動范圍

難度：中等

地上有一個 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

💡思路：廣度優先搜索

我們將行坐標和列坐標數位之和大于 k 的格子看作障礙物，那么這道題就是一道很傳統的搜索題目，我們可以使用廣度優先搜索或者深度優先搜索來解決它，本文選擇使用 廣度優先搜索 的方法來講解。

那么如何計算一個數的數位之和呢？

• 我們只需要對數 x 每次對 10 取余，就能知道數 x 的個位數是多少，然后再將 x 除 10，這個操作等價于將 x 的十進制數向右移一位，刪除個位數（類似于二進制中的 >> 右移運算符），不斷重復直到 x 為 0 時結束。

🍁代碼：(C++、Java)

C++

class Solution {
private:int getsum(int x){int ans = 0;while(x > 0 ){ans += x % 10;x /= 10;}return ans;}
public:int movingCount(int m, int n, int k) {if(k == 0) return 1;vector<pair<int, int>> dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};queue<pair<int, int>> q;q.push(make_pair(0, 0));vector<vector<int>> visited(m, vector<int>(n));visited[0][0] = 1;int ans = 1;while(!q.empty()){auto [x, y] = q.front();q.pop();for(auto dir : dirs){int cur_x = x + dir.first, cur_y = y + dir.second;if(cur_x < 0 || cur_x >= m || cur_y < 0 || cur_y >= n || visited[cur_x][cur_y] || getsum(cur_x) + getsum(cur_y) > k) continue;q.push(make_pair(cur_x, cur_y));visited[cur_x][cur_y] = 1;ans++;}}return ans;}
};

Java

class Solution {private int getsum(int x){int ans = 0;while(x > 0 ){ans += x % 10;x /= 10;}return ans;}public int movingCount(int m, int n, int k) {if(k == 0) return 1;int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};Queue<int[]> q = new LinkedList<int[]>();q.offer(new int[]{0, 0});int[][]  visited = new int[m][n];visited[0][0] = 1;int ans = 1;while(!q.isEmpty()){int[] cell = q.poll();for(int[] dir : dirs){int cur_x = cell[0] + dir[0], cur_y = cell[1] + dir[1];if(cur_x < 0 || cur_x >= m || cur_y < 0 || cur_y >= n || visited[cur_x][cur_y] == 1 || getsum(cur_x) + getsum(cur_y) > k) continue;q.offer(new int[]{cur_x, cur_y});visited[cur_x][cur_y] = 1;ans++;}}return ans;}
}

🚀 運行結果：

🕔 復雜度分析：

• 時間復雜度：$O(mn)$，其中 m 為方格的行數，n 為方格的列數。考慮所有格子都能進入，那么搜索的時候一個格子最多會被訪問的次數為常數，所以時間復雜度為$O(4mn)=O(mn)$。
• 空間復雜度：$O(mn)$，搜索的時候需要一個大小為 $O(mn)$， 的標記結構用來標記每個格子是否被走過。

題目來源：力扣。

放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關注我LeetCode主頁 / CSDN—力扣專欄，每日更新！

注： 如有不足，歡迎指正！