難度：★★★☆☆
類型：數(shù)組
方法：深度優(yōu)先搜索or寬度優(yōu)先搜索

題目

力扣鏈接請移步【本題傳送門】
更多力扣題解請移步【力扣-劍指offer目錄】

地上有一個m行n列的方格，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 。一個機器人從坐標(biāo) [0, 0] 的格子開始移動，它每次可以向左、右、上、下移動一格（不能移動到方格外），也不能進入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。例如，當(dāng)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

解答

方案1：深度優(yōu)先搜索

我們把一些功能塊封裝成函數(shù)，便于理解和使用：

neighbours(r, c)：用于獲取某個點處的所有相鄰合法點（不越界）坐標(biāo)；
digit_sum(n)：計算某個數(shù)字的各位數(shù)字之和；
can_arrive(r, c)：判斷某個點按照題目要求是否可到達；

其他注意事項：

• 遍歷過程中使用集合footprint來記錄走過的點，避免重復(fù)遍歷造成死循環(huán)；
• 深度優(yōu)先搜索函數(shù)dfs使用遞歸實現(xiàn)，開頭寫清終止條件，并在通過校驗后對相鄰點進行遍歷遞歸；
• 按照題目要求，最后返回足跡集合的長度即可。

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

        def neighbours(r, c):
            """
            獲取(r, c)所有合法相鄰位置坐標(biāo)
            """
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    yield nr, nc

        def digit_sum(n):
            """
            計算數(shù)字n各個位置之和
            """
            s = 0
            while n:
                n, r = divmod(n, 10)
                s += r
            return s

        def can_arrive(r, c):
            """
            判斷(r, c)位置是否可以到達
            """
            return digit_sum(r) + digit_sum(c) <= k

        footprint = set()           # 足跡集合
        def dfs(r, c):
            if (r, c) in footprint or not can_arrive(r, c):
                return
            footprint.add((r, c))
            for nr, nc in neighbours(r, c):
                dfs(nr, nc)

        dfs(0, 0)
        # print(footprint)
        return len(footprint)           # 所有可以到達的位置的個數(shù)



s = Solution()
print(s.movingCount(2, 3, 1))
print(s.movingCount(3, 1, 0))

方案2：寬度優(yōu)先搜索

我們把上面所述的算法用寬度優(yōu)先搜索改寫，使用隊列就可以實現(xiàn)。

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

        def neighbours(r, c):
            """
            獲取(r, c)所有合法相鄰位置坐標(biāo)
            """
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    yield nr, nc

        def digit_sum(n):
            """
            計算數(shù)字n各個位置之和
            """
            s = 0
            while n:
                n, r = divmod(n, 10)
                s += r
            return s

        def can_arrive(r, c):
            """
            判斷(r, c)位置是否可以到達
            """
            return digit_sum(r) + digit_sum(c) <= k

        queue = [(0, 0)]
        footprint = set()
        while queue:
            r, c = queue.pop(0)
            if (r, c) in footprint or not can_arrive(r, c):
                continue
            footprint.add((r, c))
            for nr, nc in neighbours(r, c):
                queue.append((nr, nc))

        return len(footprint)           # 所有可以到達的位置的個數(shù)


s = Solution()
print(s.movingCount(2, 3, 1))
print(s.movingCount(3, 1, 0))

如有疑問或建議，歡迎評論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請移步【力扣面試題解析】