题干：

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

分析：

典型的DFS或BFS的题，通过DFS＋剪枝函数直接求出可以到达的格子个数，且经过分析机器人可以只向右或者向下走。

TIPS : 找格子数量的DFS用 1 + back()的形式

答案：

class Solution {

int length;

int width;

int kValue;

int cnt = 1;

int back(int x, int y, int flag[][]) {

if (x >= length || y >= width || x < 0 || y < 0 ||

flag[x][y] == 1 || prune(x, y, kValue) == false){

return 0;

}

flag[x][y] = 1;

return 1 + back(x, y + 1, flag) + back(x+1, y, flag) +  back(x - 1, y, flag) + back(x, y - 1, flag);

}

boolean prune(int x, int y, int k) {

int sum = 0;

while (x > 0) {

sum += x % 10;

x /= 10;

}

while (y > 0) {

sum += y % 10;

y /= 10;

}

if (sum > k)

return false;

else

return true;

}

public int movingCount(int m, int n, int k) {

length = m;

width = n;

kValue = k;

int flag[][] = new int[m][n];

    return back(0, 0,flag);

    }

}