地上有一個m行n列的方格。一個機(jī)器人從坐標(biāo)(0, 0)的格子開始移動，它每一次可以向左、右、上、下移動一格，但不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。例如，當(dāng)k為18時，機(jī)器人能夠進(jìn)入方格(35, 37)，因為3+5+3+7=18。但它不能進(jìn)入方格(35, 38)，因為3+5+3+8=19。請問該機(jī)器人能夠到達(dá)多少個格子？

解析：
該題明顯使用回溯法。目標(biāo)就是從 (0,0) 這個點(diǎn)開始走，遍歷完所有能走到的方格。每個格子都可能有上、下、左、右四個方向中某幾個無法前進(jìn)，那么遇到無法前進(jìn)的就不繼續(xù)走。每次遇到一個沒有被訪問過的方格，而且這個方格可以走，那就立馬把這個格子設(shè)置成已訪問，同時把計數(shù)器加一。接下來從其他方向訪問，遇到了已經(jīng)訪問過了的方格，那直接就不去訪問就好了。思路確定了之后，想一下要實現(xiàn)的幾個函數(shù)：計算出當(dāng)前方格的那個“數(shù)位之和”的函數(shù)、檢查當(dāng)前方格能不能進(jìn)入的函數(shù)、回溯的核心函數(shù)、總的調(diào)用函數(shù)。回溯法一般使用遞歸的實現(xiàn)，在這個題就是，遇到了能訪問的就在這個方格上繼續(xù)往四周探索，不能的話就立馬終止。

答案：

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;
}