如題：

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

這道題和第12題矩陣中的路徑類似，都是在二維數(shù)組中移動，采用的方法也都是回溯法。機器人從地上的方格中移動，如果方格坐標(biāo)數(shù)位之和超過閾值，則不能走動，否則可以走，方向包括上下左右四個方向。可以畫個二維數(shù)組，從00點開始模擬走下試試。我們從00點出發(fā)，如果00點可走，則下一步有四個方向，分別是上下左右，調(diào)用遞歸四次，累加每個方向可以走動的個數(shù)。在每次走之前，需要檢查坐標(biāo)是否超出邊界，該點是否可以走以及是否已經(jīng)走過。因此，我們額外申請一個二維數(shù)組保存方格，初始化 的時候，對于每一個不能走的點置-1，對于已經(jīng)走過的點置1，可走的點置0。流程比較簡單，編碼的時候別忘了非法參數(shù)的處理。

下面是本題c++編碼：

class Solution { public://獲取數(shù)位之和int getBitSum(int val){int ret = 0;while (val){ret += val % 10;val /= 10; }return ret;}//檢查是否可走int checkThreshold(int threshold, int row, int col){int sum = getBitSum(row) + getBitSum(col);return sum > threshold ? -1 : 0;}int movingCount(vector<vector<int>> &array, int row, int col, int prow,int pcol){int cnt = 0;//檢查邊界if (prow < 0 || prow >= row || pcol < 0 || pcol >= col)return 0; //檢查是否可走if (array[prow][pcol] != 0)return 0;//可以走的話，置上標(biāo)志位cnt = array[prow][pcol] = 1;//cout<<"["<<prow<<"]["<<pcol<<"]"<<endl;//上、右、下、左cnt += movingCount(array, row, col, prow-1, pcol) + movingCount(array, row, col, prow, pcol+1) + movingCount(array, row, col, prow+1, pcol) + movingCount(array, row, col, prow, pcol-1);return cnt;}int movingCount(int threshold, int rows, int cols){vector<vector<int>> array(rows, vector<int>(cols, 0)), &rArray = array;//特殊情況處理if (threshold < 0 || (rows < 1 && cols < 1))return 0;//初始化方格for (int i = 0; i < rows; i++){for (int j = 0; j < cols; j++){array[i][j] = checkThreshold(threshold, i, j);}}//返回可到達個數(shù)return movingCount(rArray, rows, cols, 0, 0);} };

=============================================================================================

Linux應(yīng)用程序、內(nèi)核、驅(qū)動、后臺開發(fā)交流討論群(745510310)，感興趣的同學(xué)可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結(jié)

以上是生活随笔為你收集整理的《剑指offer》c++版本 13. 机器人的运动范围的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。