题目描述

[牛客网]

13. 机器人的运动范围

地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动,每一次只能向左、右、上、下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 例如,当 k 为 18 时,机器人能够进入方格 (35, 37),因为 3 + 5 + 3 + 7 = 18。但是,它不能进入方格 (35, 38),因为 3 + 5 + 3 + 8 = 19。请问该机器人能够达到多少个格子?

解法 1:xxxxxxxx

这道题跟《🗡 剑指 Offer 12. 矩阵中的路径》(本博客)很像,思路基本是一样的。

复杂度略。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        visited = [[False for c in range(cols)] for r in range(rows)]
        global ret
        ret = 0

        def sum_all_digits(n):
            s = 0
            while n > 0:
                s += n % 10
                n = n // 10
            return s

        def movingCount_helper(i, j):
            if (i >= 0 and i < rows and j >= 0 and j < cols and not visited[i][j] and
                sum_all_digits(i) + sum_all_digits(j) <= threshold):
                global ret
                ret += 1
                visited[i][j] = 1
                movingCount_helper(i + 1, j)
                movingCount_helper(i - 1, j)
                movingCount_helper(i, j + 1)
                movingCount_helper(i, j - 1)

        movingCount_helper(0, 0)
        return ret
  • 运行时间:28ms
  • 占用内存:5756k