每日一题：Leetcode 面试题13.机器人的运动范围

比眉伴天荒 2023-07-10 14:17 18阅读 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

**示例 1**：

输入：m = 3, n = 1, k = 0  
输出：1

**提示**：

1 <= n,m <= 100
    0 <= k <= 20

## 题解： ##

**题目难度**：中等  
**解题思路**：

本题目是一道DFS或者BFS的题目。

首先题意我们不难理解，即找出二维矩阵中的所有**能到达的**、**坐标数据分解之和不大于给定值K**的所有格子即可。

作者一开始的思路是遍历，即从左到右、从上到下遍历一遍，并对每个格子是否符合要求单独判断。错误的代码如下：  
**错误代码：**

func movingCount(m int, n int, k int) int { 
    	var count int
    	for i := 0 ; i < m ; i ++ { 
    		if splitData(i,0) > k { 
    			break
    		}
    		for j := 0 ; j < n ; j ++ { 
    			if splitData(i,j) > k { 
    				break
    			} else { 
    				count ++
    			}
    		}
    	}
    	return count
    }
    
    func splitData(m int, n int) int { 
    	sum := 0
    	for ; m > 0 ; m /= 10 { 
    		sum += m%10
    	}
    	for ; n > 0 ; n /= 10 { 
    		sum += n%10
    	}
    	return sum
    }

事实上，这种暴力遍历的做法忽略了对机器人实际运动的仿真性，即有可能有的点是可以联通的，但是被我们剪枝剪掉了。因此，我们需要认真研究一下机器人的运动轨迹。我们假设长度m和宽度n均为20，并通过图像来观察在不同k值下机器人的运动范围的变化。

图片作者：jyd 链接：[https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/][https_leetcode-cn.com_problems_ji-qi-ren-de-yun-dong-fan-wei-lcof_solution_mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70]当k的值为6时，我们发现，虽然整个二维矩阵有四块区域满足机器人的判断条件，但是有三块并不连通，也就意味着当k比较小的时候，机器人的活动范围只有一块位于左上角的三角形的区域。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70 1]随着k的不端正增加，我们发现机器人已经能够接触到右上角和左下角的三角形区域了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70 2]k继续增加，我们会发现k已经能够贯通所有区域了。

因此，本题的解题思路就是DFS或者BFS。本人在这里给出一种DFS的解法，即上下左右四种方向依次回溯，剪枝条件为：访问过的点不可达，越界的点不可达，数位和大于k的点不可达。其余可达的点返回1，最后累加起来，就是我们所需的答案。

话不多说，直接放码。

**AC代码：**

func movingCount(m int, n int, k int) int { 
    	// 首先初始化一个二维数组，用于标记二维矩阵的每个格子是否已经走过了。
    	visit := make([][]bool, m + 1)
    	for i := 0; i < len(visit); i++ { 
    		visit[i] = make([]bool, n + 1)
    	}
    	//进行深搜。
    	return dfs(0, 0, m, n, k, visit)
    }
    
    // 本函数用于对二维矩阵进行深度优先搜索。
    func dfs(x, y, m, n, k int, visit [][]bool) int { 
    	if x >= m || y >= n || x < 0 || y < 0 { 
    		return 0 // 如果这个地方越界了，就返回。
    	}
    	if visit[x][y] { 
    		return 0 // 如果这个地方已经被访问过了，就返回。
    	}
    	if splitData(x, y) > k { 
    		return 0 // 如果这个地方的坐标拆分之和不满足题目要求，就返回。
    	}
    	visit[x][y] = true //标记自己已经走过这个格子了。
    	sum := 1
    	// 深度优先搜索法，按四个方向进行搜索，并累积满足要求的格子数量。
    	sum += dfs(x - 1, y, m, n, k, visit)
    	sum += dfs(x + 1, y, m, n, k, visit)
    	sum += dfs(x, y - 1, m, n, k, visit)
    	sum += dfs(x, y + 1, m, n, k, visit)
    	return sum
    }
    
    // 本函数用于对坐标的值进行按位拆分，并求和。
    func splitData(m int, n int) int { 
    	sum := 0
    	for ; m > 0 ; m /= 10 { 
    		sum += m%10
    	}
    	for ; n > 0 ; n /= 10 { 
    		sum += n%10
    	}
    	return sum
    }

事实上，我们没有必要上下左右四个方向全走一遍。我们仅保留“向下”和“向右”两种走法也是可以的，并且占用内存更少。

// 改进后的dfs函数，只用往下走和往右走。
    func dfs(x, y, m, n, k int, visit [][]bool) int { 
    	if x >= m || y >= n || x < 0 || y < 0 { 
    		return 0 // 如果这个地方越界了，就返回。
    	}
    	if visit[x][y] { 
    		return 0 // 如果这个地方已经被访问过了，就返回。
    	}
    	if splitData(x, y) > k { 
    		return 0 // 如果这个地方的坐标拆分之和不满足题目要求，就返回。
    	}
    	visit[x][y] = true //标记自己已经走过这个格子了。
    	sum := 1
    	// 深度优先搜索法，按四个方向进行搜索，并累积满足要求的格子数量。
    	// sum += dfs(x - 1, y, m, n, k, visit)
    	sum += dfs(x + 1, y, m, n, k, visit)
    	//sum += dfs(x, y - 1, m, n, k, visit)
    	sum += dfs(x, y + 1, m, n, k, visit)
    	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_solution_mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b]: https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030310041144.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200303100726418.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200303100737755.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2,size_16,color_FFFFFF,t_70