剑指Offer：机器人的运动范围

剑指Offer：机器人的运动范围

问题描述：
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

这个题目与 矩阵中的路径 很类似。

解题思路：

1. 只是确定能够走多少格子，并且把走过的格子排除；
2. 通过走过一个格子后，将其赋值一个标识符，为了防止二次访问；
3. 通过递归思想，进行遍历，边界条件设定好，在每次递归函数中，增加一个加数器nums；
4. 四种递归函数全部都遍历完，把不符合的再淘汰即可。

注意：
k==0时，直接返回1；

class Solution {
public:
    int nums=0;		//全局变量
    int movingCount(int m, int n, int k) 
    {
        vector<vector<int> > data(m, vector<int>(n, 0));   //将二维数组全部赋值为0
        if (k==0)
        {
            return 1;
        }
        mvcount(m, n, k, data, 0, 0);
        return nums;
    }

private:
    void mvcount(int m, int n, int k, vector<vector<int> > &data, int i, int j)
    {
    	/* 注意数组越界， 这里若不包含m,n会指针出错 */
        if (i>=m || j>=n || i<0 || j<0)
        {
            return;
        }
        /* 提取十进制的个位和十位数 */
        if ((i%10+i/10+j%10+j/10) > k)
        {
            return;
        }
        if (data[i][j]==1)
        {
            return;
        }
        data[i][j]=1;
        nums++;

        mvcount(m, n, k, data, i+1, j);
        mvcount(m, n, k, data, i-1, j);          
        mvcount(m, n, k, data, i, j+1);
        mvcount(m, n, k, data, i, j-1);
    }       
};