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

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

解析：
该题明显使用回溯法。目标就是从 (0,0) 这个点开始走，遍历完所有能走到的方格。每个格子都可能有上、下、左、右四个方向中某几个无法前进，那么遇到无法前进的就不继续走。每次遇到一个没有被访问过的方格，而且这个方格可以走，那就立马把这个格子设置成已访问，同时把计数器加一。接下来从其他方向访问，遇到了已经访问过了的方格，那直接就不去访问就好了。思路确定了之后，想一下要实现的几个函数：计算出当前方格的那个“数位之和”的函数、检查当前方格能不能进入的函数、回溯的核心函数、总的调用函数。回溯法一般使用递归的实现，在这个题就是，遇到了能访问的就在这个方格上继续往四周探索，不能的话就立马终止。

答案：

int getDigitSum(int number)
{
    int cnt = 0;
    while (number>0)
    {
        cnt += number%10;
        number /= 10;
    }
    return cnt;
}

inline bool check(int threshold, unsigned int rows, unsigned int cols, \
            unsigned int row, unsigned int col, const bool* visited)
{
    return row<rows && col<cols && row>=0 && col>=0 && \
    !visited[row*cols+col] && threshold>=(getDigitSum(row)+getDigitSum(col));
}

int movingCountCore(int threshold, unsigned int rows, unsigned int cols, \
                unsigned int row, unsigned int col, bool* visited)
{
    int cnt = 0;
    if (check(threshold, rows, cols, row, col, visited))
    {
        visited[row * cols + col] = true;
        cnt = 1+movingCountCore(threshold, rows, cols, row, col+1, visited)+ \
                movingCountCore(threshold, rows, cols, row, col-1, visited)+ \
                movingCountCore(threshold, rows, cols, row+1, col, visited)+ \
                movingCountCore(threshold, rows, cols, row-1, col, visited);
    }
    return cnt;
}

int movingCount(int threshold, unsigned int rows, unsigned int cols)
{
    if(threshold<0 || rows<=0 || cols<=0) return 0;
    bool *visited = new bool[rows*cols];
    memset(visited, false, rows*cols);

    int count = movingCountCore(threshold, rows, cols, 0, 0, visited);

    delete[] visited;
    return count;
}