机器人的运动范围(剑指offer 13) Java深度优先遍历

目录

一、题目描述

二、思路讲解

三、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;
    }
}

上一篇:儿童六角数独


下一篇:django 路由传参