《剑指offer》练习及解析(C++代码)13-16

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

解法：

1.回溯法

一种搜索方法，每次选择一个方向向前搜索，直到到达最优目标或确定无法达到目标时，后退重新向未选择的方向前进。

用二维数组记录是否走过此位置，且每次只需向下或向右行进即可

代码：

//My solution 回溯
//24ms:6.5 ;10mb:100, O(n)
class Solution {
public:
    const vector<vector<int>> step={
  {1,0},{0,1}};
    int movingCount(int m, int n, int k) {
        vector<vector<int>> ismov(m, vector<int>(n,0));
        ismov[0][0]=1;
        int sum=1;
        move(m,n,k,0,0,ismov, sum);
        return sum;
    }
    //回溯过程
    void move(int m, int n, int k,