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

兴趣爱好交流 每日一题
1

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

转化成字符串来求和，

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
3 
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有数量的限制呢

4

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

5 
class Solution8:
@classmethod
def movingCount(cls, m: int, n: int, k: int) -> int:
    
    # 正确构造m*n矩阵的方法
    cls.counted = [[0 for _ in range(n)] for _ in range(m)]
    cls.count = 0

    def dfs(k, i, j):
        # 若越界或不满足条件，则结束dfs深度遍历        
        if not 0 <= i < m or not 0 <= j < n or (i // 10 + i % 10 + j // 10 + j % 10) > k:
            return False
        # 若未越界并满足条件，但该位置已被遍历过
        elif 0 <= i < m and 0 <= j < n and (i // 10 + i % 10 + j // 10 + j % 10) <= k and cls.counted[i][j] == 1:
            return False
        # 若未越界并满足条件，且该位置并未被遍历过，则计数+1
        elif 0 <= i < m and 0 <= j < n and (i // 10 + i % 10 + j // 10 + j % 10) <= k and cls.counted[i][j] == 0:
            cls.count += 1
            # 标记该位置已被遍历过
            cls.counted[i][j] = 1
        # 进行向右方和下方的遍历
        if dfs(k, i + 1, j) or dfs(k, i, j + 1):
            return True

    # 从[0,0]开始遍历
    dfs(k, 0, 0)
    return cls.count
6 
def sum_bit(m,n):
    list_a = []
    sum_mn = 0
    list_a.extend(str(m))
    list_a.extend(str(n))
    for i in range(len(list_a)):
        sum_mn += int(list_a[i])
    return sum_mn


def robot_solution(m, n, k):
    if m < 1 or m > 100 or n < 1 or n > 100 or k < 0 or k > 20:
        print("请输入正确范围内的m,n,k （1 <= n,m <= 100，0 <= k <= 20）")
        return

    list_mn = []
    for i in range(m):
        for j in range(n):
            sum_mn = sum_bit(i, j)
            if sum_mn <= k:
                list_mn.append((i, j))
    num = len(list_mn)
    return num