目录

一、题目描述

二、思路讲解

三、Java代码实现

四、时空复杂度分析

五、代码优化 

        1、不需要向上和向左搜索 

        2、 数位求和无需循环

        3、函数传值还可简化

一、题目描述

        地上有一个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。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：

1 <= n,m <= 100
0 <= k <= 20

二、思路讲解

        对于我这种算法小白来说，看见在矩阵中上下左右跑的，直接无脑深搜。

        从（0，0）开始，像上下左右方向分别找满足条件的节点，如果某一个方向满足条件，就走到这个位置，继续找这个位置的上下左右（递归）；如果某一个方向不满足条件，应该排除掉这个方向（剪枝操作）。当四个方向都找完之后，回到上一个节点（回溯）。

为了避免走“回头路”，避免将已经访问过的节点再算上去，我们定义一个二位数组visited，来标记是否访问过。

然后是确定跳出递归的条件：

        1、超出边界；

        2、数位之和大于k；

        3、已经被访问过。

三、Java代码实现

class Solution {
    public int movingCount(int m, int n, int k) {
        //用来标记该位置是否访问过 为1则访问过
        int [][]visited = new int[m][n];

        return dfs(0, 0, m, n, k, 0, visited);
    }

    public static int dfs(int i, int j, int m, int n, int k, int count, int [][]visited) {
    	
        //如果指针越界 或 行列数位之和大于k 或 被访问过，则直接返回count次数
    	if(i<0 || j<0 || i>=m || j>=n || fun(i, j)>k || visited[i][j]==1) {
    		return count;
    	}
    	
        //将当前位置标记为已访问
    	visited[i][j] = 1;
        //满足条件的格子数+1
    	count++;
    	
    	count = dfs(i-1, j, m, n, k, count, visited); //往上找
    	count = dfs(i+1, j, m, n, k, count, visited); //往下找
    	count = dfs(i, j-1, m, n, k, count, visited); //往左找
    	count = dfs(i, j+1, m, n, k, count, visited); //往右找
    	
    	return count;
    }

    //用来计算坐标为（m，n）的数位之和
    public static int fun(int m, int n){
        int sum = 0;
        while(m!=0){
            sum = sum + m%10;
            m = m/10;
        }
        while(n!=0){
            sum = sum + n%10;
            n = n/10;
        }
        return sum;
    }
}

四、时空复杂度分析

        时间复杂度：        O(MN)        最坏情况下，机器人遍历整个矩阵

        空间复杂度：        O(MN)        最坏情况下，visited矩阵存储所有单元格的索引

五、代码优化 

        1、不需要向上和向左搜索 

        由于机器人从左上角出发，所以他只会往右或往下走，因此不需要向上和向左搜索。

        2、 数位求和无需循环

        由于题目中矩阵的坐标都是一位或者两位数，要想求这样数字的数位和只需要x%10 + x/10即可 。

        3、函数传值还可简化

        其实dfs中不需要把count传进去计算所有满足条件的格子数量，只需要返回这一支的满足条件的数量就行了。 

class Solution {
    public int movingCount(int m, int n, int k) {
        //用来标记该位置是否访问过 为1则访问过
        int [][]visited = new int[m][n];

        return dfs(0, 0, m, n, k, visited);
    }

    public static int dfs(int i, int j, int m, int n, int k, int [][]visited) {
    	
        //如果指针越界 或 行列数位之和大于k 或 被访问过，则直接返回count次数
    	if(i<0 || j<0 || i>=m || j>=n || fun(i, j)>k || visited[i][j]==1) {
    		return 0;
    	}
    	
        //将当前位置标记为已访问
    	visited[i][j] = 1;
        //         往下找                          往右找          	
    	return 1 + dfs(i+1, j, m, n, k, visited) + dfs(i, j+1, m, n, k, visited);
    }

    //用来计算坐标为（m，n）的数位之和
    public static int fun(int m, int n){
        return m%10 + m/10 + n%10 + n/10;
    }
}