|
| 1 | +''' |
| 2 | +地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 |
| 3 | +例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。 |
| 4 | +但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？ |
| 5 | +''' |
| 6 | + |
| 7 | +# -*- coding:utf-8 -*- |
| 8 | +class Solution: |
| 9 | + def movingCount(self, threshold, rows, cols): |
| 10 | + visited = [False] * (rows * cols) |
| 11 | + count = self.movingCountCore(threshold, rows, cols, 0, 0, visited) |
| 12 | + return count |
| 13 | + |
| 14 | + def movingCountCore(self, threshold, rows, cols, row, col, visited): |
| 15 | + count = 0 |
| 16 | + if self.check(threshold, rows, cols, row, col, visited): |
| 17 | + visited[row * cols + col] = True |
| 18 | + count = 1 + self.movingCountCore(threshold, rows, cols, row-1, col, visited) + \ |
| 19 | + self.movingCountCore(threshold, rows, cols, row+1, col, visited) + \ |
| 20 | + self.movingCountCore(threshold, rows, cols, row, col-1, visited) + \ |
| 21 | + self.movingCountCore(threshold, rows, cols, row, col+1, visited) |
| 22 | + return count |
| 23 | + |
| 24 | + def check(self, threshold, rows, cols, row, col, visited): |
| 25 | + if row >= 0 and row < rows and col >= 0 and col < cols and self.getDigitSum(row) + self.getDigitSum(col) <= threshold and not visited[row * cols + col]: |
| 26 | + return True |
| 27 | + return False |
| 28 | + |
| 29 | + def getDigitSum(self, number): |
| 30 | + sum = 0 |
| 31 | + while number > 0: |
| 32 | + sum += (number % 10) |
| 33 | + number = number // 10 |
| 34 | + return sum |
| 35 | + |
| 36 | +s = Solution() |
| 37 | +print(s.movingCount(5, 10, 10)) |
0 commit comments