剑指offer【机器人运动范围-DFS/BFS】

地上有一个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。请问该机器人能够到达多少个格子？

DFS

参照矩阵中的路径：

• 剪枝：遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为「可行性剪枝」 。
• 递归参数：当前的matrix的索引 i,j； 当前想要匹配的字符索引 k
• 终止条件：1. 数位只和>k 2. 越界 3. 当前已访问过；
• 递归：只向右侧&下侧去找
  可达解分析/数位更新规则分析：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/
• 回溯返回值：下方可达解个数+右侧可达解个数+1（自身）
• 最终结果 dfs(0,0,0,0)

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        visited = set()
        def dfs(i,j,si,sj):
            # 当前坐标[i][j]，i的数位和si，j的数位和sj
            if i>=m or j>=n or si+sj > k or (i,j) in visited:
                return 0
            else:
                # 加入visited
                visited.add((i,j))
                new_si = si + 1 if (i + 1) % 10 else si - 8
                new_ji = sj + 1 if (j + 1) % 10 else sj - 8
                return 1 + dfs(i+1,j,new_si,sj) + dfs(i,j+1,si,new_ji)
                    #  自己 + 下方个数 + 右方个数
        return dfs(0,0,0,0)

BFS

广度优先遍历，使用队列queue实现

• 出队的时候，判断是否符合基本要求，符合放入visited（基本要求同上，索引未超、未访问、<k）
• 出队的时候，把它的右侧和下方放入队列
• 最终返回出队且符合要求的visited，Len(visited)

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        visited = set()
        queue = [] # 空队列
        queue.append((0,0,0,0))    # 加入starting
        while queue:
            # 出队
            i,j,si,sj = queue.pop()
            # 判断出队的是否符合要求
            if  i>=m or j>=n or si+sj > k or (i,j) in visited:
                continue
            visited.add((i,j))
            # 递归，把右侧和下方的元素放到队列中
            new_si = si + 1 if (i + 1) % 10 else si - 8
            new_ji = sj + 1 if (j + 1) % 10 else sj - 8
            queue.append((i+1,j,new_si,sj))
            queue.append((i,j+1,si,new_ji))

        return len(visited)