剑指 Offer 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

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

解题思路

首先，这个题不能简单的把坐标拆开判断是不是符合和<=k，因为在坐标为(10, 9)的时候，此时的坐标和比之前的(9, 9)还要小！所以需要根据之前走过的路径判断能不能走到坐标大于10的某个位置
1.dfs+剪枝
写一个dfs函数，不断递归一下新坐标，看看是不是符合要求。
使用python的时候，通常可以使用set来进行剪枝，目的是递归的时候不要走重复的路径。set中可以直接add((x, y))
2.bfs
bfs的核心是看看每一层和当前相邻的节点（右边或下边的）有没有符合条件的，有的话把相邻的节点加入队列，并把当前的节点算作结果的计数。当队列为空，输出最终结果。
在这种方法中，将符合条件的相邻坐标添加入队列的同时，也需要把这个相邻坐标添加进visited set，从而避免多种路径经过同一个坐标（比如(3, 3)可能从(2, 3)进，也可能从(3, 2)进）。

解题代码

方法1

class Solution:
    def divideBit(self, num: int):
        return int(num/10), num%10

    def movingCount(self, m: int, n: int, k: int) -> int:
        visited = set()
        def dfs(x, y):
            if x >= m or y >= n or (x, y) in visited:
                return
            a, b = self.divideBit(x)
            c, d = self.divideBit(y)
            if a + b <= k and c + d <= k and a + b + c + d <= k:
                visited.add((x, y))
                dfs(x + 1, y)
                dfs(x, y + 1)
        dfs(0, 0)
        return len(visited)

方法2

class Solution:
    def divideBit(self, num: int):
        return int(num/10), num%10

    def movingCount(self, m: int, n: int, k: int) -> int:
        count = 0
        queue = [(0, 0)]
        visited = set()
        x, y = 0, 0
        while queue:
            (x, y) = queue.pop(0)
            count += 1
            if x + 1 < m and y < n:  # 限制x增长的边界
                if sum(self.divideBit(x+1)) + sum(self.divideBit(y)) <= k and (x+1, y) not in visited:
                    queue.append((x+1, y))
                    visited.add((x+1, y))
            if x < m and y + 1 < n:  # 限制y增长的边界
                if sum(self.divideBit(x)) + sum(self.divideBit(y+1)) <= k and (x, y+1) not in visited:
                    queue.append((x, y+1))
                    visited.add((x, y+1))
        return count

执行结果

方法一
执行结果：通过
执行用时：48 ms, 在所有 Python3 提交中击败了60.88%的用户
内存消耗：15.6 MB, 在所有 Python3 提交中击败了36.99%的用户
方法二
执行结果：通过
执行用时：48 ms, 在所有 Python3 提交中击败了60.88%的用户
内存消耗：15.2 MB, 在所有 Python3 提交中击败了85.02%的用户