机器人的运动范围

1.题目描述2.思路3.代码4.总结

思路类似于矩阵的路径，类似于矩阵上的遍历。基本思路就是矩阵的遍历加上回溯方法。回溯方法依赖于visited[i][j]矩阵，如果遍历过就结束。基本的代码模板是dfs函数递归加回溯。

public class 机器人的运动范围 {
    int res = 0;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        dfs(0,0,m,n,k);
        return res;
    }

    public void dfs(int i,int j,int m, int n,int k){
        if (i<0||i>m-1||j<0||j>n-1||getSum(i)+getSum(j)>k||visited[i][j]) {
            return;
        }
        if (i>=0&&i<=m-1&&j>=0&&j<=n-1&&getSum(i)+getSum(j)<=k&&!visited[i][j]) {
            visited[i][j] = true;
            res++;
        }
        dfs(i+1,j,m,n,k);
        dfs(i-1,j,m,n,k);
        dfs(i,j+1,m,n,k);
        dfs(i,j-1,m,n,k);
    }

    public int getSum(int k){
        int tmp = 0;
        while (k!=0){
            tmp += k % 10;
            k /= 10;
        }
        return tmp;
    }
}

矩阵dfs遍历加回溯