【LeetCode】剑指 Offer 13. 机器人的运动范围 p92 -- Java Version

题目链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

1. 题目介绍（13. 机器人的运动范围）

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

2. 题解

2.1 回溯（DFS+剪枝）-- O(mn)

时间复杂度O(mn)，空间复杂度O(mn)

• 深度优先搜索： 可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推，过程如上图所示。
• 剪枝： 在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为 可行性剪枝 。

class Solution {// 1. 从[0,0]位置起始出发// 2. 向方格四面八方判断// 3. 统计机器人可到达的格子总数public int movingCount(int m, int n, int k) {// 错误判断if (m <= 0 || n <= 0 || k < 0) return 0;// 辅助数组：用来标记当前格子是否被访问过boolean[][] visited = new boolean[m][n];// 从（0，0）开始出发return dfs(0,0,m,n,k,visited);}public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {// 递归终止条件：错误判断if(i >= m || j >= n || k <getDigitSum(i) + getDigitSum(j) || visited[i][j]) return 0;// 该位置通过了错误判断，说明该方格属于机器人可达visited[i][j] = true;// 当前格 + 往下走 + 往右走,因为是0出发，不是从任意点出发，所以这里就不需要从四个方向都进行相加return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited);}// 求一个非负整数的数位之和public int getDigitSum(int number){int sum = 0;while (number > 0){sum += number % 10;number = number/10;}return sum;}}

2.2 BFS – O(mn)

时间复杂度O(mn)，空间复杂度O(mn)

class Solution {public int movingCount(int m, int n, int k) {boolean[][] visited = new boolean[m][n];int res = 0;Queue<int[]> queue= new LinkedList<int[]>();queue.add(new int[] { 0, 0, 0, 0 });while(queue.size() > 0) {int[] x = queue.poll();int i = x[0], j = x[1], si = x[2], sj = x[3];if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;visited[i][j] = true;res ++;queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });}return res;}
}

3. 参考资料

[1] 剑指 Offer 13. 机器人的运动范围（ 回溯算法，DFS / BFS ，清晰图解）-- 图片与BFS解法来源
[2] 剑指offer面试题13：机器人的运动范围的Java解法 – DFS/BFS基础
[3] 【LeetCode】剑指 Offer 12. 矩阵中的路径 p89 – Java Version – 相似题目