剑指 Offer 13. 机器人的运动范围

主要用到的思路和矩阵的路径一样，都是dfs加回溯，和求岛屿数量是一类型题
1：利用visited[][]来标记该点是否被访问过，因为要求格子的数量，肯定不能记录重复的格子，相当于岛屿的沉没
2：在dfs函数中，首先确定递归结束的条件：
（1）：超出边界
（2）：k<sum
(3)visited[i][j]==true,该节点已经被访问过
然后就是在上下左右四个方向开始不断的递归

class Solution {
public int movingCount(int m, int n, int k) {
    //临时变量visited记录格子是否被访问过
    boolean[][] visited = new boolean[m][n];
    return dfs(0, 0, m, n, k, visited);
}

public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
    //i >= m || j >= n是边界条件的判断，k < sum(i, j)判断当前格子坐标是否
    // 满足条件，visited[i][j]判断这个格子是否被访问过
    if (i<0||j<0||i >=m || j >=n || k < sum(i, j) || visited[i][j])
        return 0;
    //标注这个格子被访问过
    visited[i][j] = true;
    //沿着当前格子的右边和下边继续访问
    return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited)+dfs(i - 1, j, m, n, k, visited)+dfs(i , j-1, m, n, k, visited);
}

//计算两个坐标数字的和
private int sum(int i, int j) {
    int sum = 0;
    while (i != 0) {
        sum += i % 10;
        i /= 10;
    }
    while (j != 0) {
        sum += j % 10;
        j /= 10;
    }
    return sum;
}

}