剑指offer 机器人的运动范围

Posted on |

题目

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

方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        visited=[False]*(rows*cols)
        count=self.movingCountCore(threshold, rows, cols, 0, 0, visited)
        return count

    def movingCountCore(self, threshold, rows, cols, row, col, visited):
        count=0
        if self.check(threshold, rows, cols, row, col, visited):
            visited[row*cols+col]=True
            count=1+self.movingCountCore(threshold, rows, cols, row+1, col, visited)+ \
            self.movingCountCore(threshold, rows, cols, row-1, col, visited)+ \
            self.movingCountCore(threshold, rows, cols, row, col+1, visited)+ \
            self.movingCountCore(threshold, rows, cols, row, col-1, visited)
        return count
    def check(self, threshold, rows, cols, row, col, visited):
        if 0<=row<rows and 0<=col<cols and not visited[row*cols+col] and \
        self.geiDigitSum(row)+self.geiDigitSum(col)<=threshold:
            return True
        return False
    def geiDigitSum(self,num):
        sum=0
        while num>0:
            sum+=num%10
            num=num/10
        return sum

请注意，两个整数相加不能写成sum(a,b)，会出现问题TypeError: 'int' object is not iterable