剑指offer-66、机器⼈的运动范围
<h2 id="题目描述">题目描述</h2><p>地上有⼀个 m ⾏和 n 列的⽅格。⼀个机器⼈从坐标（0,0） 的格⼦开始移动，每⼀次只能向左，右，上，下四个⽅向移动⼀格，但是不能进⼊⾏坐标和列坐标的数位之和⼤于 k 的格⼦。 例如，当k 为 18 时，机器⼈能够进⼊⽅格（35,37） ，因为 3+5+3+7 = 18 。但是，它不能进⼊⽅格（35,38） ，因为 3+5+3+8 = 19 。请问该机器⼈能够达到多少个格⼦？</p>
<p>示例1</p>
<p>输⼊：5,10,10<br>
返回值：21</p>
<p>示例2</p>
<p>输⼊：10,1,100<br>
返回值：29</p>
<p>说明：,,,,,,,,,,,,,,,,,,,,,,,,,,,, 这29种，后⾯的 , 以及 等等是⽆法到达的。</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="dfs深度优先搜索">DFS（深度优先搜索）</h3>
<p>深度优先搜索算法，也就是 DFS ,⾸先需要初始化数组，注意是 boolean 类型的⼆元数组。边初始化<br>
边计算位数的和，判断如果⼤于等于阈值的话，就直接置为 true ，也就是已经被访问到（但是这⼀部分计⼊结果）。</p>
<p>然后遍历每⼀个元素，只要 i ， j 不在合法的索引范围或者是已经被访问过，都会直接返回<br>
false 。</p>
<p>否则的话，可访问的数量 +1 ，并且递归遍历上下左右四个元素，返回最终的可访问的个数。</p>
<p>DFS 会优先同⼀个⽅向，⼀直⾛下去，不撞南墙不回头，直到条件不满⾜的时候，才会回头。回头之后，每次只会回头⼀步，往另外⼀个⽅向去，同样是⼀头扎进去。</p>
<p>假设有⼀个 4 x 4 的⽅格，从第⼀个开始遍历，假设遍历顺序是上，右，下，左，那么遍历的顺序如下：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503161749049.png" alt="" loading="lazy"></p>
<pre><code class="language-java">public class Solution {
public int movingCount(int threshold, int rows, int cols) {
if (rows > 0 && cols > 0) {
boolean[][] visited = new boolean;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 如果⼤于阈值，设置已被访问过
visited = ((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.length ||
visited) {
return count;
}
count++;
visited = 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;
}
}
</code></pre>
<ul>
<li>时间复杂度：最坏的情况是将所有的格⼦都遍历⼀遍， O(m*n) 。</li>
<li>空间复杂度：借助了额外的空间保存是否被访问过，同样为O(m*n) 。</li>
</ul>
<h3 id="bfs度优先搜索">BFS（⼴度优先搜索）</h3>
<p>⼴度优先搜索，也就是没进⾏⼀步，优先搜索当前点的各个⽅向上的点，不急着往下搜索，等搜索完当前点的各个⽅向的点，再依次把之前搜索的点，取出来，同样先搜索周边的点...</p>
<p>这样直到所有都被搜索完成。</p>
<p>同样有⼀个 4 x 4 的⽅格，从第⼀个开始遍历，假设遍历顺序是上，右，下，左，那么遍历的顺序如下：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503161805645.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503161805902.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503161805292.png" alt="" loading="lazy"></p>
<p>在上⾯的过程图示中，我们可以发现，访问是有顺序的，每遍历⼀个新的⽅块，都会标⼀个顺序，然后按照顺序遍历其四个⽅向。</p>
<p>这也就是⼴度优先搜索的本质，我们需要⼀个队列，来保存遍历的顺序，每次都从队列⾥⾯取出⼀个位置，遍历其四周的⽅块，每次遍历到的点，都会放到队列⾥⾯，这样直到队列为空的时候，也就是全部遍历完成。</p>
<pre><code class="language-java">import java.util.LinkedList;
import java.util.Queue;
public class Solution13 {
public int movingCount(int threshold, int rows, int cols) {
boolean[][] visited = new boolean;
int count = 0;
Queue<int[]> queue = new LinkedList<>();
// 把第⼀个点加到队列⾥⾯
queue.add(new int[]{0, 0});
while (queue.size() > 0) {
// ⼀直取数据，直到队列为空
int[] x = queue.poll();
// 取出来的数据，包含x，y坐标
int i = x, j = x;
// 如果访问过或者不符合，直接下⼀个
if (i >= rows || j >= cols || threshold < getSum(i) + getSum(j) || visited) continue;
// 置为访问过
visited = 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;
}
}
</code></pre>
<ul>
<li>时间复杂度：最坏的情况是将所有的格⼦都遍历⼀遍， O(m*n) 。</li>
<li>空间复杂度：借助了额外的空间保存是否被访问过，同样为O(m*n) 。</li>
</ul>
<h3 id="动态规划最优解">动态规划（最优解）</h3>
<p>利用递推关系式，避免重复计算。</p>
<ul>
<li>格子(i,j)可达 ⇔ 数位和满足条件 ∧ (左边格子可达 ∨ 上边格子可达)</li>
<li>dp表示(i,j)是否可达，基于左边和上边格子的状态：<code>dp = (digitSum(i) + digitSum(j) ≤ k) && (dp || dp)</code></li>
</ul>
<pre><code class="language-java">public class Solution {
public int movingCount(int m, int n, int k) {
if (k == 0) return 1;
// dp表示格子(i,j)是否可达
boolean[][] dp = new boolean;
dp = 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 |= dp;// 从上边来
}
if (j - 1 >= 0) {
dp |= dp;// 从左边来
}
// 如果当前格子可达，计数加1
count += dp ? 1 : 0;
}
}
return count;
}
private int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(mn)，双重循环遍历所有格子</li>
<li><strong>空间复杂度</strong>：O(mn)，dp数组的空间</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19495582
頁:
[1]