剑指 day 5【JZ13 机器人的运动范围】回溯深入

剑指 day 5【JZ13 机器人的运动范围】回溯深入

1. DFS，往四个方向移动，额外使用一个visitflag记录是否已经到达该小格子。最后对visitflag求和即可。

class Solution:
    def movingCount(self , threshold: int, rows: int, cols: int) -> int:
        visitflag = [[0]*cols for _ in range(rows)]
        def sumNum(number):
            sumnum = 0
            while number>0:
                sumnum += number % 10
                number //= 10
            return sumnum
        def dfs(i, j, visitflag):
            if 0<=i 
后来发现其实不用四个方向，因为起始点是(0, 0)，因此只要右和下两个方向即可。并且也可以用一个count去记录visit的小格，后面就无需对二维数组求和。此外，由于函数是定义在函数体里面的，visitflag可以作为一个全局变量，无需作为参数传入，可以在函数内部直接使用。
 优化后的代码如下，时间都少了一半。
 
class Solution:
    def movingCount(self , threshold: int, rows: int, cols: int) -> int:
        visitflag = [[0]*cols for _ in range(rows)]
        count = 0
        def sumNum(number):
            sumnum = 0
            while number>0:
                sumnum += number % 10
                number //= 10
            return sumnum
        def dfs(i, j):
            count = 0
            if 0<=i 
2. BFS
 
from collections import deque
class Solution:
    def movingCount(self , threshold: int, rows: int, cols: int) -> int:
        def sumNum(number):
            sumnum = 0
            while number>0:
                sumnum += number % 10
                number //= 10
            return sumnum
            
        q = deque()
        q.append((0,0))
        count = 0
        visitflag = [[0]*cols for _ in range(rows)]
        visitflag[0][0] = 1
        while q:
            i, j = q.popleft()
            count += 1
            for i,j in [(i+1,j),(i,j+1)]:
                if 0<=i
欢迎分享，转载请注明来源：内存溢出
原文地址:https://www.54852.com/zaji/5610814.html