剑指offer 面试题13. 机器人的运动范围（中）

如何对一个问题进行回溯算法建模？回溯算法解题，必须考虑优化策略！

Tag

回溯算法

题目

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

1
2
输入：m = 2, n = 3, k = 1
输出：3
示例 2： 
1
2
输入：m = 3, n = 1, k = 0
输出：1

提示： 1 <= n,m <= 100 0 <= k <= 20

直觉

这道题还有一个隐藏的优化：我们在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索。如下图，我们展示了 16 * 16 的地图随着限制条件 k 的放大，可行方格的变化趋势，每个格子里的值为行坐标和列坐标的数位之和，蓝色方格代表非障碍方格，即其值小于等于当前的限制条件 k。

注意，如果不做优化，Python写的回溯，遇到[100, 100, 20]这个测试用例就会调用栈溢出。回溯算法解题，必须考虑优化策略！

代码

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import unittest
from typing import List

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        """
        :param m: rows
        :param n: cols
        :param k:
        :return int:
        """
        rows = m 
        cols = n
        if rows <= 0 or cols <= 0 or k < 0: return 0
        if k == 0: return 1
        visited = [[True for _ in range(cols)] for _ in range(rows)]

        def digitsum(n):
            res = 0
            while n:
                res += n % 10
                n //= 10
            return res

        def backtrack(row=0, col=0):
            count = 0
            if 0 <= row < rows and 0 <= col < cols and visited[row][col] and (digitsum(row) + digitsum(col)) <= k:
                visited[row][col] = False
                # 如果不做优化，Python写的回溯，遇到[100, 100, 20]这个测试用例就会调用栈溢出。
                # count = 1 + backtrack(row-1, col) + \
                #     backtrack(row, col-1) + \
                #     backtrack(row+1, col) + \
                #     backtrack(row, col+1)
                # 搜索方向可以缩减为向右和向下，搜索方向可以缩减为向右和向下。
                count = 1 + backtrack(row+1, col) + backtrack(row, col+1)
            return count

        count = backtrack()
        return count


class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        # 1 <= `n,m` <= 100
        # 0 <= `k` <= 20
        inputs = [
            [2, 3, 1],  # 功能测试
            [3, 3, 3],
            [3, 1, 0],  # 边界测试
            [1, 3, 1],
            [100, 100, 20],
            [0, 0, 20],  # 特殊输入样例 []
        ]
        answers = [3, 8, 1, 2, 6117, 0]  # 
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.movingCount(inputs[i][0], inputs[i][1], inputs[i][2]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        from queue import Queue
        q = Queue()
        q.put((0, 0))
        s = set()
        while not q.empty():
            x, y = q.get()
            if (x, y) not in s and 0 <= x < m and 0 <= y < n and digitsum(x) + digitsum(y) <= k:
                s.add((x, y))
                for nx, ny in [(x + 1, y), (x, y + 1)]:
                    q.put((nx, ny))
        return len(s)

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/ji-qi-ren-de-yun-dong-fan-wei-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        vis = set([(0, 0)])
        for i in range(m):
            for j in range(n):
                if ((i - 1, j) in vis or (i, j - 1) in vis) and digitsum(i) + digitsum(j) <= k:
                    vis.add((i, j))
        return len(vis)

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/ji-qi-ren-de-yun-dong-fan-wei-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。