剑指Offer 13 机器人的运动范围

墨蓝 2021-12-19 04:19 180阅读 0赞

[机器人的运动范围][Link 1]

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

1 # -*- coding:utf-8 -*-
     2 class Solution:
     3     def __init__(self):
     4         self.visited = []
     5         self.count = 0
     6         
     7     def bfs(self,threshold,rows,cols,i,j,direction):
     8         if i < 0 or i >= rows or j < 0 or j >= cols:
     9             return
    10         elif self.visited[i][j] == 1:
    11             return
    12         else:
    13             self.visited[i][j] = 1
    14             num = 0
    15             for n1 in str(i):
    16                 num += int(n1)
    17             for n2 in str(j):
    18                 num += int(n2)
    19             if num <= threshold:
    20                 self.count += 1
    21                 for direct in direction:
    22                     x = i+direct[0]
    23                     y = j+direct[1]
    24                     self.bfs(threshold,rows,cols,x,y,direction)
    25         
    26     def movingCount(self, threshold, rows, cols):
    27         self.visited = [[0 for c in range(cols)]for r in range(rows)]
    28         direction = [[0,1],[0,-1],[1,0],[-1,0]]
    29         self.bfs(threshold,rows,cols,0,0,direction)
    30         return self.count
    31         # write code here

转载于:https://www.cnblogs.com/asenyang/p/11014510.html

[Link 1]: https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&tqId=11219&tPage=4&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking