剑指 Offer 13. 机器人的运动范围

思路

将行坐标和列坐标数位之和大于 k 的格子看作障碍物，那么这道题就是一道很传统的搜索题目，这里使用dfs进行搜索。

这道题还有一个隐藏的优化：我们在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索。

根据题意可推知，任意一个格子都可以由其上方格子向下走过来，或者由其左方的格子向右走过来，因此我们可以将我们的搜索方向缩减为向右或向下。

代码实现

 1 class Solution {
 2 private:
 3     vector<vector<bool>> vis;
 4     int ans = 0;
 5 public:
 6     int movingCount(int m, int n, int k) {
 7         vis = vector<vector<bool>>(m, vector<bool>(n, false));
 8         dfs(m, n, k, 0, 0);
 9         return ans;
10     }
11 
12     //获取一个数的各个数位之和
13     int getBitSum(int num) {
14         int sum = 0;
15         while(num) {
16             sum += num % 10;
17             num /= 10;
18         }
19 
20         return sum;
21     }
22 
23     //获取一个坐标的数位之和
24     int getCoordinateSum(int x, int y) {
25         return getBitSum(x) + getBitSum(y);
26     }
27 
28     void dfs(int m, int n, int k, int x, int y) {
29 
30         if(x < 0 || y < 0 || x >= m || y >= n || vis[x][y] || getCoordinateSum(x, y) > k) 
31             return;
32        
33         vis[x][y] = true;
34         ans++;
35 
36         //优化：只需要考虑向右走和向下走
37         dfs(m, n, k, x+1, y);
38         dfs(m, n, k, x, y+1);
39     }
40 
41 };

复杂度分析

参考

力扣官方题解-机器人的运动范围