剑指offer系列55：机器人的运动范围

这个题目的思路跟上一个很相似，还是回溯法。就是从第一个框开始判断是否大于限定值，然后判断它的上下左右。这个题可以明显看出来判断出来的应该是左上方区域，所以从0作为起点也很适合。

回溯法似乎很喜欢用递归，做题的时候注意边界值的处理。

 1 class Solution {
 2 public:
 3     int movingCount(int threshold, int rows, int cols)
 4     {
 5         if (threshold < 0 || rows <= 0 || cols <= 0)
 6             return 0;
 7         bool *visited = new bool[rows*cols];
 8         memset(visited, 0, rows*cols);
 9         int count = getcount(threshold, rows, cols, 0, 0, visited);
10         delete[]visited;
11         return count;
12     }
13     int getcount(int threshold, int rows, int cols, int row, int col, bool *visit)//主函数
14     {
15         int count = 0;
16         if (row>=0&&row < rows&&col>=0&&col < cols && !visit[row*cols + col] && digitsum(threshold, row, col))
17         {
18             count++;
19             visit[row*cols + col] = true;
20             count += getcount(threshold, rows, cols, row, col + 1, visit)
21                 + getcount(threshold, rows, cols, row + 1, col, visit)
22                 + getcount(threshold, rows, cols, row - 1, col, visit)
23                 + getcount(threshold, rows, cols, row, col - 1, visit);
24         }
25         return count;
26 
27     }
28     bool digitsum(int threshold, int row, int col)
29     {
30         if (digitcomp(threshold, row)+digitcomp(threshold, col)<=threshold)
31             return true;
32         return false;
33     }
34     int digitcomp(int threshold, int n)
35     {
36         int sum=0;
37         while (n)
38         {
39             sum += n % 10;
40             n /= 10;
41         }
42         return sum;
43     }
44 };

这道题是剑指offer 的最后一个题了。我写的这个系列博客也进入了尾声。大部分题我都写出来了，少部分题目没有是因为我最开始是在github上写的。写代码在乎一个练，要天天动手。预计下个月刷第二遍，还会写一些关于算法和设计模式的内容。愿大家都能找到心仪的工作ヾ(◍°∇°◍)ﾉﾞ