題目：地上有一個m行和n列的方格。一個機(jī)器人從坐標(biāo)0,0的格子開始移動叶沛，每一次只能向左蒲讯，右，上灰署，下四個方向移動一格判帮，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 例如溉箕，當(dāng)k為18時晦墙，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18肴茄。但是晌畅，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19寡痰。請問該機(jī)器人能夠達(dá)到多少個格子踩麦？
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
boolean[][] flag = new boolean[rows][cols];
return helper(0, 0, rows, cols, threshold, flag);
}
public int helper(int i, int j, int rows,int cols, int threshold, boolean[][] flag){
if(i < 0 || j < 0 || i >= rows || j >= cols || flag[i][j] || (getSum(i) + getSum(j) > threshold)){
return 0;
}
flag[i][j] = true;
return helper(i- 1, j, rows, cols, threshold, flag)
+ helper(i, j - 1, rows, cols, threshold, flag)
+ helper(i + 1, j, rows, cols, threshold, flag)
+ helper(i , j + 1, rows, cols, threshold, flag) + 1;
}
int getSum(int x){
int sum = 0;
while( x != 0){
sum += (x + 10) % 10;
x /= 10;
}
return sum;
}
}
按照題意，設(shè)定一個表示已走格子的二維數(shù)組氓癌，如果走過了那么在該點(diǎn)表true谓谦，通過遞歸表示分別向上下左右行走，當(dāng)出現(xiàn)越界或者不符合題意不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子則退出該行走分支贪婉，也是該遞歸分支的結(jié)束條件反粥，不斷嘗試，走過的點(diǎn)更改標(biāo)記疲迂，直到無路可走才顿，所有遞歸分支都碰壁。(走過的格子數(shù)是通過返回值來傳遞的尤蒿，所以在向四個方向行走后加1郑气，表示訪問了當(dāng)前格子)
