面试题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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题目比起79-WordSearch要简单很多。题目要求是符合要求的格子总数，所以每个格子可以走多次。本题用BFS比DFS更适合。这样我们能得出一个直观的解题思路：

从原点(0,0)开始，只要满足和小于K，就标记为True。最后只需要遍历整个mxn矩阵，计算出所有True的个数即可。

79-WordSearch是找路径问题，所以不仅需要标注状态，还要需要回溯，然后状态重置。

解法

class Solution:
	directions = [(0,-1),(-1,0),(0,1),(1,0)]
	def movingCount(self, m: int, n: int, k: int) -> int:
		marked = [[False  for _ in  range(n)] for _ in  range(m)]
		self.__move(0, 0, marked, m, n, k)
		result = 0
		for i in  range(m):
			for j in  range(n):
				if marked[i][j] == True:
					result += 1
		return result

	def __move(self,start_x, start_y, marked, m, n, k):
		str_start = str(start_x) + str(start_y)
		sum_start = 0
		for i in  range(len(str_start)):
			sum_start += int(str_start[i])
		if sum_start <= k:
			marked[start_x][start_y] = True
			# examine next point
			for direction in  self.directions:
				new_x = start_x + direction[0]
				new_y = start_y + direction[1]
				if  0<= new_x <m and  0<= new_y <n and 					not marked[new_x][new_y]:
					self.__move(new_x, new_y, marked, m, n, k)

在当前节点(start_x, start_y)符合要求的情况下，以其为基础，遍历周围四个方向的相邻节点是否符合要求；若是发现了符合要求的点，继续检查相邻节点。这就是迭代

优化

如何计算一个数的数位之和呢？

我们只需要对数 x 每次对 10 取余，就能知道数 x 的个位数是多少；然后再将 x 除 10，这个操作等价于将 x 的十进制数向右移一位，删除个位数（类似于二进制中的 >> 右移运算符），不断重复直到 x 为 0 时结束。

隐藏的优化

我们在搜索的过程中，搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索。在这个回答中，展示了 16 * 16 的地图随着限制条件 k 的放大，可行方格的变化趋势，每个格子里的值为行坐标和列坐标的数位之和，蓝色方格代表非障碍方格，即其值小于等于当前的限制条件 k。
我们可以发现随着限制条件 k 的增大，(0, 0) 所在的蓝色方格区域内新加入的非障碍方格都可以由上方或左方的格子移动一步得到。
而其他不连通的蓝色方格区域会随着 k 的增大而连通，且连通的时候也是由上方或左方的格子移动一步得到，因此我们可以将我们的搜索方向缩减为向右或向下。

下面给出的参考代码使用了queue，也就是队列。主要有queue.put()和queue.get()方法。解决的思路是：
设置了一个集合s保存符合要求的节点；设置一个队列保存要判断的节点。最后通过计算集合s中的个数，得到符合要求的个数。

一般而言，BFS搜索问题都会用到队列的方法来解决。

def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        from queue import Queue
        q = Queue()
        q.put((0, 0))
        s = set()
        while not q.empty():
            x, y = q.get()
            if (x, y) not in s and 0 <= x < m and 0 <= y < n and digitsum(x) + digitsum(y) <= k:
                s.add((x, y))
                for nx, ny in [(x + 1, y), (x, y + 1)]:
                    q.put((nx, ny))
        return len(s)

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/ji-qi-ren-de-yun-dong-fan-wei-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个方法的效率不及自己的方法。当然，上面两条优化方法对于自己的代码的优化还是很大的。

递推法

考虑到搜索的方向只需要朝下或朝右，我们可以得出一种递推的求解方法。

定义vis[i][j]为(i, j)坐标是否可达，如果可达返回 1，否则返回 0。

首先 (i, j) 本身需要可以进入，因此需要先判断 i 和 j 的数位之和是否大于 k ，如果大于的话直接设置vis[i][j]为不可达即可。

否则，前面提到搜索方向只需朝下或朝右，因此 (i, j) 的格子只会从 (i - 1, j) 或者 (i, j - 1) 两个格子走过来（不考虑边界条件），那么vis[i][j]是否可达的状态则可由如下公式计算得到：

\(\textit{vis}[i][j]=\textit{vis}[i-1][j]\ \textrm{or}\ \textit{vis}[i][j-1]\)

即只要有一个格子可达，那么 (i, j) 这个格子就是可达的，因此我们只要遍历所有格子，递推计算出它们是否可达然后用变量 ans 记录可达的格子数量即可。

初始条件 vis[i][j] = 1 ，递推计算的过程中注意边界的处理。

def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        vis = set([(0, 0)])
        for i in range(m):
            for j in range(n):
                if ((i - 1, j) in vis or (i, j - 1) in vis) and 	                digitsum(i) + digitsum(j) <= k:
                    vis.add((i, j))
        return len(vis)

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/ji-qi-ren-de-yun-dong-fan-wei-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个方法的效率和自己的代码的效率类似。