描述

地上有一个rows行和cols列的方格。坐标从 [0,0] 到 [rows-1,cols-1]。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于threshold的格子。 例如，当threshold为18时，机器人能够进入方格[35,37]，因为3+5+3+7 = 18。但是，它不能进入方格[35,38]，因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？   求解思路：

1. 首先确定DFS的思路，
2. 一个格子有上下左右四个方向，但其实我们只需要关注右下两个方向就行

代码：

 1 class Solution {
 2 private:
 3     int count=0;
 4 public:
 5     int movingCount(int threshold, int rows, int cols) {
 6         if(threshold<=0){
 7             return 1;
 8         }
 9         // 能用向量尽量用向量，初始化都简单很多
10 //         bool** flag=new bool*[rows];
11 //         for(int i=0;i<rows;++i){
12 //             flag[i]=new bool[cols];
13 //             for(int j=0;j<cols;++j){
14 //                 flag[i][j]=false;
15 //             }
16 //         }
17         vector<vector<bool>> flag(rows,vector<bool>(cols,false));
18         DFS(threshold,flag,0,0,rows,cols);
19         return count;
20     }
21     
22     // count已经是成员变量了，不需要返回
23     // 递归中改变参数的值：静态变量、成员变量、引用
24     void DFS(int ths,vector<vector<bool>>& flag, int x,int y,int rs,int cs){
25         if(getSum(x,y)>ths || rs<=x || cs<=y || flag[x][y]){
26             return;
27         }
28         flag[x][y]=true;
29         count+=1;
30         DFS(ths,flag,x+1,y,rs,cs); // 只需关注向右递归
31         DFS(ths,flag,x,y+1,rs,cs); // 只需关注向下递归
32     }
33     
34     // 计算两个数字的位数和
35     int getSum(int nr,int nc){
36         int res=0;
37         while(nc>0){
38             res+=nc%10;nc/=10;
39         }
40         while(nr>0){
41             res+=nr%10;nr/=10;
42         }
43         return res;
44     }
45 };

心得：

1. 递归中改变参数的三种方式：成员变量、静态变量、引用
2. 尽量用向量而非数组
3. 尽量让代码更简介（如计算两个数字的位数之和，明显有冗余代码），更有逻辑性。