難度：★★★☆☆
類型：數(shù)組
方法：深度優(yōu)先搜索or寬度優(yōu)先搜索
題目
力扣鏈接請(qǐng)移步【本題傳送門】
更多力扣題解請(qǐng)移步【力扣-劍指offer目錄】
地上有一個(gè)m行n列的方格叹哭，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 卡辰。一個(gè)機(jī)器人從坐標(biāo) [0, 0] 的格子開始移動(dòng)砸捏，它每次可以向左躺屁、右舅踪、上抚岗、下移動(dòng)一格（不能移動(dòng)到方格外）雇庙，也不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子瞧甩。例如钉跷，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格 [35, 37] 肚逸，因?yàn)?+5+3+7=18爷辙。但它不能進(jìn)入方格 [35, 38]彬坏，因?yàn)?+5+3+8=19。請(qǐng)問該機(jī)器人能夠到達(dá)多少個(gè)格子膝晾？
示例 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)：用于獲取某個(gè)點(diǎn)處的所有相鄰合法點(diǎn)（不越界）坐標(biāo)；
digit_sum(n)：計(jì)算某個(gè)數(shù)字的各位數(shù)字之和血当；
can_arrive(r, c)：判斷某個(gè)點(diǎn)按照題目要求是否可到達(dá)幻赚；
其他注意事項(xiàng)：
- 遍歷過程中使用集合footprint來記錄走過的點(diǎn)，避免重復(fù)遍歷造成死循環(huán)臊旭；
- 深度優(yōu)先搜索函數(shù)dfs使用遞歸實(shí)現(xiàn)落恼，開頭寫清終止條件，并在通過校驗(yàn)后對(duì)相鄰點(diǎn)進(jìn)行遍歷遞歸离熏；
- 按照題目要求佳谦，最后返回足跡集合的長(zhǎng)度即可。
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):
"""
計(jì)算數(shù)字n各個(gè)位置之和
"""
s = 0
while n:
n, r = divmod(n, 10)
s += r
return s
def can_arrive(r, c):
"""
判斷(r, c)位置是否可以到達(dá)
"""
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) # 所有可以到達(dá)的位置的個(gè)數(shù)
s = Solution()
print(s.movingCount(2, 3, 1))
print(s.movingCount(3, 1, 0))
方案2：寬度優(yōu)先搜索
我們把上面所述的算法用寬度優(yōu)先搜索改寫撤奸，使用隊(duì)列就可以實(shí)現(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):
"""
計(jì)算數(shù)字n各個(gè)位置之和
"""
s = 0
while n:
n, r = divmod(n, 10)
s += r
return s
def can_arrive(r, c):
"""
判斷(r, c)位置是否可以到達(dá)
"""
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) # 所有可以到達(dá)的位置的個(gè)數(shù)
s = Solution()
print(s.movingCount(2, 3, 1))
print(s.movingCount(3, 1, 0))
如有疑問或建議，歡迎評(píng)論區(qū)留言~
有關(guān)更多力扣中等題的python解決方案胧瓜，請(qǐng)移步【力扣面試題解析】
