面试题13：机器人的运动范围

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

代码：里面有具体分析

class Solution {
public:
    /*
    int count_sum(int n);
    int findGrid(int threshold, int rows, int cols, int row, int col, bool* visited);
    */
    //计算一个数各位数之和
    int count_sum(int n)
    {
        int count = 0;
        while (n > 0)
        {
            int temp = n % 10;
            count += temp;
            n = n / 10;
        }
        return count;
    }

    int movingCount(int threshold, int rows, int cols)
    {
        //若初始参数不满足，返回空
        if (threshold < 0 || rows <= 0 || cols <= 0)
            return NULL;
        //访问矩阵:以一维数组方式表示二维数组元素
        bool* visited = new bool[rows * cols];
        //初始化visited数组为false
        memset(visited, false, rows * cols);

        //指定返回值，从（0,0）处开始进入迭代
        int count=findGrid(threshold, rows, cols,0,0, visited);
        //销毁访问矩阵
        delete[] visited;
        return count;
    }

    /*主要遍历部分：指定计数变量count_grids记录遍历各个满足条件的格子数量，
    注意这一题与面试题12矩阵中的路径一题不同，此题不能直接遍历所有格子，因为机器人threshod限制，根本跳不上去
    所以不能设置一个记录步数，遍历完整个矩阵方程就结束的标志，而是前后左右一步步试探，若满足条件则计数变量加1，
    否则放弃此节点。遍历到最后不满足if条件就返回计数值。
    */
    int findGrid(int threshold, int rows, int cols, int row, int col,bool* visited)
    {
        //计数变量
        int count_grids = 0;
        /*
        若当前点(row,col)满足条件可以继续前后左右遍历；
        条件有：row,col处于正确范围；row,col各位数之和不大于threshold；（row,col）未被访问。
        */
        if (row >= 0 && row < rows && col >= 0 && col < cols
            && count_sum(row)+count_sum(col) <= threshold 
            && !visited[row * cols + col])
        {
            //访问[row,col]节点，达到要求的格子数量+1,访问标志置为true
            visited[row * cols + col] = true;
            count_grids++;
            //这里很重要！！！直接加上满足条件的当前格子的前后左右即可，与上题不同啊。
            count_grids=count_grids+
                findGrid(threshold, rows, cols, row, col - 1, visited) +
                findGrid(threshold, rows, cols, row, col + 1, visited)+
                findGrid(threshold, rows, cols, row - 1, col, visited)+
                findGrid(threshold, rows, cols, row + 1, col, visited);
        }
        return count_grids;
    }
};

更新，方式一样，讲解有差异

这次的主要差错是将moveSum这个返回变量，也是全局变量当成 Move的参数了，它是从头到尾计算的格子数量，不是每个格子的属性，所以注意！

//求出一个数的位数之和
int getDigitSum(int digit)
{
    if (digit < 0)
        return 0;
    if (digit >= 0 && digit <= 9)
        return digit;
    int sum = 0;
    while (digit > 0)
    {
        sum += (digit % 10);
        digit = digit / 10;
    }
    return sum;
}

int GetGrids(int m, int n, int k)
{
    if (m < 0 || n < 0 || k < 0)
        return 0;
    //访问矩阵
    vector<vector<bool> >visit(m, vector<bool>(n, false));
    int result = Move(m, n, k, 0, 0, visit);
    return result;
}
//从起点startX,start开始能够遍历的格子的总数
int Move(int m, int n, int k,int startX,int startY,vector<vector<bool> >&visit)
{
    //!!!!!!这是个总数，不能放入Move参数中作为每个遍历的起始点
    int moveSum = 0;
    int digitSum = getDigitSum(startX) + getDigitSum(startY);
    //cout << "startX=" << startX << "  " << "startY=" << startY << " " << "digitSum=" << digitSum << endl;
    if (!(startX >= 0 && startX < m && startY >= 0 && startY < n &&
        visit[startX][startY] == false && digitSum <= k))
        return 0;

    //若当前格子满足条件，则计数加1，并向下遍历    
    visit[startX][startY] = true;
    moveSum = 1 + Move(m, n, k, startX - 1, startY, visit) +
        Move(m, n, k, startX + 1, startY, visit) +
        Move(m, n, k, startX, startY - 1, visit) +
        Move(m, n, k, startX, startY + 1, visit);
    //cout << moveSum << endl;
    return moveSum;
}

int main()
{
    int m = 4, n = 4, k = 1;
    cout << GetGrids(m, n, k) << endl;
    return 0;
}