剑指 Offer 13. 机器人的运动范围

Difficulty
Medium
Tags
回溯
DFS
URL
https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
Star
地上有一个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

法1 dfs

思路
从入口开始一直往下遍历即可。注意判断条件是进入下一层后写，还是进入前就写。
建议是进入下一层后载统一写判断条件，如果不满足条件直接return即可，这样的好处是代码整洁，即只有一处为判断条件
题解
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        used = [[False] * n for _ in range(m)]
        self.dfs(m=m, n=n, row=0, col=0, used=used, k=k)
        return sum(map(sum,used)) 

    def dfs(self, m, n, row, col, used, k):
        if row >= m or col >= n or row < 0 or col < 0:
            return
        # 走过的就不走了
        if used[row][col]:
            return
        if row // 100 + row % 100 // 10 + row % 10 + \
            col // 100 + col % 100 // 10 + col % 10 > k:
            return
        # print(row, col)
        used[row][col] = True
        # 向左
        self.dfs(m, n, row+1, col, used, k)
        self.dfs(m, n, row-1, col, used, k)
        self.dfs(m, n, row, col+1, used, k)
        self.dfs(m, n, row, col-1, used, k)

法 2 BFS

思路
BFS才应该是最容易理解的，将能到达的节点添加到队列中，每次出队的时候 res += 1
题解
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        queue = collections.deque()
        queue.append((0,0))
        visited = [[False] * n for _ in range(m)]
        visited[0][0] = True

        res = 0

        dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))
        while queue:
            cur = queue.popleft()
            res += 1

            # 遍历四周
            for d in dirs:
                x = cur[0] + d[0]
                y = cur[1] + d[1]
                if (m > x >= 0 and 
                    n > y >= 0 and 
                    not visited[x][y] and
                    self.is_valid(x, y, k)):

                    queue.append((x, y))
                    visited[x][y] = True

        return res

    def is_valid(self, x, y, k):
        temp = 0
        while x > 0:
            temp += x % 10
            x //= 10

        while y > 0:
            temp += y % 10
            y //= 10

        return temp <= k