您好,登錄后才能下訂單哦!
題目描述
地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開(kāi)始移動(dòng),每一次只能向左,右,上,下四個(gè)方向移動(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)問(wèn)該機(jī)器人能夠達(dá)到多少個(gè)格子?
class Solution:
def movingCount(self, threshold, rows, cols):
# 判斷(row, col)是否可以進(jìn)入:位置合法且未進(jìn)入過(guò)
def isValid(row, col):
if row < 0 or row >= rows or col < 0 or col >= cols:
return False
num = 0
while row > 0:
num += row % 10
row //= 10
while col > 0:
num += col % 10
col //= 10
return num <= threshold
def helper(row, col):
cnt = 0 # 對(duì)于每個(gè)位置,在確認(rèn)過(guò)可以訪問(wèn)之前先初始化為0
if isValid(row, col) and not visited[row][col]:
# 如果(row, col)可以進(jìn)入,那么將其設(shè)為已訪問(wèn),然后對(duì)四個(gè)鄰居進(jìn)行訪問(wèn)
visited[row][col] = True
cnt = (1 + helper(row + 1, col) + helper(row - 1, col)
+ helper(row, col + 1) + helper(row, col - 1))
return cnt
if threshold < 0:
return 0
visited = [[False] * cols for _ in range(rows)]
return helper(0, 0)
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。