剑指offer-机器人的运动范围(DFS)

描述

地上有一个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. 尽量让代码更简介(如计算两个数字的位数之和,明显有冗余代码),更有逻辑性。
上一篇:性能分析之 SQL 性能分析(MySQL)


下一篇:扫雷优化版