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

￡神魔★判官ぃ 2022-12-17 03:27 131阅读 0赞

# 题目 #

地上有一个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

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof][https_leetcode-cn.com_problems_ji-qi-ren-de-yun-dong-fan-wei-lcof]

# 解题思路 #

本题思路使用回溯法/深度优先遍历dfs

需要注意的点:

*  计算数位之和
 *  有的方格虽然能满足数位之和的要求,但是由于中间有的方格机器人不能通过,所以这部分机器人也不能够到达
 *  虽然有四个移动方向,但是由于是从左上角开始移动的,所以可以优化为向右和向下两个方向

深度遍历几个终止条件:

*  下标越界
 *  已经被访问
 *  数位之和不满足

# 代码 #

class Solution { 
        public int movingCount(int m, int n, int k) { 
            // 本题思路:回溯/深度优先遍历dfs
            // 这个地方有个需要明确的点
            // 有的方格虽然能满足数位之和的要求,但是由于中间有的方格机器人不能通过,所以这部分机器人也不能够到达
            // 创建一个二维数组,用来标识当前位置是否已被访问过
            boolean[][] used = new boolean[m][n];
            return dfs(0, 0, m, n, k, used);
        }
    
        private int dfs(int i, int j, int m, int n, int k, boolean[][] used) { 
            // 下标越界,已被访问,数位之和不满足
            if (i >= m || j >= n || used[i][j] || getSum(i) + getSum(j) > k) { 
                return 0;
            }
    
            // 标识为已使用
            used[i][j] = true;
            // 虽然有四个移动方向,但是由于是从左上角开始移动的,所以可以优化为向右和向下两个方向
            return 1 + dfs(i + 1, j, m, n, k, used) + dfs(i, j + 1, m, n, k, used);
        }
    
        private int getSum(int x) { 
            // 计算数位之和
            int sum = 0;
            while (x != 0) { 
                sum += x % 10;
                x /= 10;
            }
            return sum;
        }
    }

[https_leetcode-cn.com_problems_ji-qi-ren-de-yun-dong-fan-wei-lcof]: https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof