剑指Offer13-机器人的运动范围

地上有一个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

一解

采用回溯法,与剑指offer12类似,需要注意以下几点:

  • Python多维数组不要使用[[False] * n]*m,其表示浅拷贝,改变一个值,其它值会同步被修改

class Solution:

    def movingCount(self, m: int, n: int, k: int) -> int:

        tmp = [[False for _ in range(n)] for _ in range(m)]

        def dfs(i, j):

            if i < 0 or i >= m or j < 0 or j >= n or  (i//10 + i%10 + j//10 + j%10) > k or tmp[i][j]:

                return 0

            tmp[i][j] = True

            # 从 [0, 0] 到 [m-1, n-1] ,只需向右下角移动即可

            return dfs(i + 1, j) + dfs(i, j + 1) + 1

            

        return dfs(0, 0)

转化成字符串来求和,

def robotrun(m,n,k):
    res=0
    if n<1 or m>100 or k<0 or k>20:
        return '参数取值范围错误'
    else:
        for i in range(m):
            ii=str(i)
            sum1=0
            for x in ii:
                sum1=sum1+int(x)
            for j in range(n):
                jj=str(j)
                sum2=0
                for y in jj:
                    sum2=sum2+int(y)
                sum=sum1+sum2
                if sum<=k:
                    res=res+1
        return res
def solution(m: int, n: int, k: int):
    result = 0

    def cal(num: int) -> int:
        r = 0
        while num > 0:
            num, r = num // 10, r + (num % 10)
        return r

    for i in range(m):
        for j in range(n):
            if (cal(i) + cal(j)) <= k:
                result += 1
    return result


assert solution(2, 3, 1)
assert solution(3, 1, 0)

为什么m,n有数量的限制呢

数量太大的话,服务器无法计算

关闭