题目描述
地上有⼀个 m ⾏和 n 列的⽅格。⼀个机器⼈从坐标（0,0） 的格⼦开始移动，每⼀次只能向左，右，上，下四个⽅向移动⼀格，但是不能进⼊⾏坐标和列坐标的数位之和⼤于 k 的格⼦。 例如，当k 为 18 时，机器⼈能够进⼊⽅格（35,37） ，因为 3+5+3+7 = 18 。但是，它不能进⼊⽅格（35,38） ，因为 3+5+3+8 = 19 。请问该机器⼈能够达到多少个格⼦？
示例1
输⼊：5,10,10
返回值：21
示例2
输⼊：10,1,100
返回值：29
说明：[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后⾯的[0,29] , [0,30] 以及[0,31] 等等是⽆法到达的。
思路及解答
DFS（深度优先搜索）
深度优先搜索算法，也就是 DFS ,⾸先需要初始化数组，注意是 boolean 类型的⼆元数组。边初始化
边计算位数的和，判断如果⼤于等于阈值的话，就直接置为 true ，也就是已经被访问到（但是这⼀部分计⼊结果）。
然后遍历每⼀个元素，只要 i ， j 不在合法的索引范围或者是已经被访问过，都会直接返回
false 。
否则的话，可访问的数量 +1 ，并且递归遍历上下左右四个元素，返回最终的可访问的个数。
DFS 会优先同⼀个⽅向，⼀直⾛下去，不撞南墙不回头，直到条件不满⾜的时候，才会回头。回头之后，每次只会回头⼀步，往另外⼀个⽅向去，同样是⼀头扎进去。
假设有⼀个 4 x 4 的⽅格，从第⼀个开始遍历，假设遍历顺序是上，右，下，左，那么遍历的顺序如下：
- public class Solution { public int movingCount(int threshold, int rows, int cols) { if (rows > 0 && cols > 0) { boolean[][] visited = new boolean[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { // 如果⼤于阈值，设置已被访问过 visited[i][j] = ((getSum(i) + getSum(j)) > threshold); } } return getNum(visited, 0, 0, 0); } return 0; } // 获取可以被访问的个数 private int getNum(boolean[][] visited, int i, int j, int count) { if (i < 0 || j < 0 || i >= visited.length || j >= visited[0].length || visited[i][j]) { return count; } count++; visited[i][j] = true; count = getNum(visited, i, j + 1, count); count = getNum(visited, i, j - 1, count); count = getNum(visited, i + 1, j, count); count = getNum(visited, i - 1, j, count); return count; } // 计算位数之和 private int getSum(int num) { int result = 0; while (num > 0) { result = result + num % 10; num = num / 10; } return result; }}
- 时间复杂度：最坏的情况是将所有的格⼦都遍历⼀遍， O(m*n) 。
- 空间复杂度：借助了额外的空间保存是否被访问过，同样为O(m*n) 。
BFS（⼴度优先搜索）
⼴度优先搜索，也就是没进⾏⼀步，优先搜索当前点的各个⽅向上的点，不急着往下搜索，等搜索完当前点的各个⽅向的点，再依次把之前搜索的点，取出来，同样先搜索周边的点...
这样直到所有都被搜索完成。
同样有⼀个 4 x 4 的⽅格，从第⼀个开始遍历，假设遍历顺序是上，右，下，左，那么遍历的顺序如下：
在上⾯的过程图示中，我们可以发现，访问是有顺序的，每遍历⼀个新的⽅块，都会标⼀个顺序，然后按照顺序遍历其四个⽅向。
这也就是⼴度优先搜索的本质，我们需要⼀个队列，来保存遍历的顺序，每次都从队列⾥⾯取出⼀个位置，遍历其四周的⽅块，每次遍历到的点，都会放到队列⾥⾯，这样直到队列为空的时候，也就是全部遍历完成。- import java.util.LinkedList;import java.util.Queue;public class Solution13 { public int movingCount(int threshold, int rows, int cols) { boolean[][] visited = new boolean[rows][cols]; int count = 0; Queue queue = new LinkedList(); // 把第⼀个点加到队列⾥⾯ queue.add(new int[]{0, 0}); while (queue.size() > 0) { // ⼀直取数据，直到队列为空 int[] x = queue.poll(); // 取出来的数据，包含x，y坐标 int i = x[0], j = x[1]; // 如果访问过或者不符合，直接下⼀个 if (i >= rows || j >= cols || threshold < getSum(i) + getSum(j) || visited[i][j]) continue; // 置为访问过 visited[i][j] = true; // 数量增加 count++; // 右 queue.add(new int[]{i + 1, j}); // 下 queue.add(new int[]{i, j + 1}); } return count; } // 计算位数之和 private int getSum(int num) { int result = 0; while (num > 0) { result = result + num % 10; num = num / 10; } return result; }}
- 时间复杂度：最坏的情况是将所有的格⼦都遍历⼀遍， O(m*n) 。
- 空间复杂度：借助了额外的空间保存是否被访问过，同样为O(m*n) 。
动态规划（最优解）
利用递推关系式，避免重复计算。
- 格子(i,j)可达 ⇔ 数位和满足条件 ∧ (左边格子可达 ∨ 上边格子可达)
- dp[j]表示(i,j)是否可达，基于左边和上边格子的状态：dp[j] = (digitSum(i) + digitSum(j) ≤ k) && (dp[i-1][j] || dp[j-1])
- public class Solution { public int movingCount(int m, int n, int k) { if (k == 0) return 1; // dp[i][j]表示格子(i,j)是否可达 boolean[][] dp = new boolean[m][n]; dp[0][0] = true; // 起点可达 int count = 1; // 起点已计入 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 跳过起点和数位和超限的情况 if ((i == 0 && j == 0) || digitSum(i) + digitSum(j) > k) { continue; } // 检查是否可以从左边或上边到达当前格子 if (i - 1 >= 0) { dp[i][j] |= dp[i - 1][j]; // 从上边来 } if (j - 1 >= 0) { dp[i][j] |= dp[i][j - 1]; // 从左边来 } // 如果当前格子可达，计数加1 count += dp[i][j] ? 1 : 0; } } return count; } private int digitSum(int num) { int sum = 0; while (num > 0) { sum += num % 10; num /= 10; } return sum; }}
- 时间复杂度：O(mn)，双重循环遍历所有格子
- 空间复杂度：O(mn)，dp数组的空间
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
