剑指66-机器人的运动范围

Posted on | In |

题目描述

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

  • 用一个长度为m*n的列表来存储同样数量的方格是否访问，可以一一对应。访问效率和字典一样，应该比字典开销低一些，简单一些。
  • 用一个全局变量记录已经访问的方格的数量。
  • 用一个全局变量列表来记录每个方格是否已经被访问过。
  • 边界检测要在被调用的子函数find里做。如果在movingCount里做，需要为四个调用分别做边界检测，麻烦且容易出错。
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
class Solution:
    def find(self, r, c):
        if r < 0 or c < 0 or r >= self.rows or c >= self.cols or self.logs[r*self.cols+c]:
            return
        else: 
            self.logs[r*self.cols+c] = True
        #if sum(map(int, str(r)+str(c))) <= self.threshold:
        if sum([int(s) for s in str(r)+str(c)]) <= self.threshold:
            self.count += 1 
            # 如果格子(r,c)符合条件，则查询其四周的格子
            self.find(r-1, c)
            self.find(r+1, c)
            self.find(r, c-1)
            self.find(r, c+1)
    
    def movingCount(self, threshold, rows, cols):
        self.rows = rows
        self.cols = cols
        self.threshold = threshold
        self.logs = [False]*(self.rows*self.cols) # 记载已经找到的格子
        self.count = 0 # 已经找到的可以到达的格子数量
        
        self.find(0, 0) # 从(0,0)位置开始找

        return self.count
  • 递归函数直接递归计算能够访问的节点数。思路与剑指offer38-二叉树的深度类似。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def find(self, r, c):
        if r < 0 or c < 0 or r >= self.rows or c >= self.cols or self.logs[r*self.cols+c]:
            return 0
        else: 
            self.logs[r*self.cols+c] = True
            if sum(map(int, str(r)+str(c))) <= self.threshold:
                return 1 + self.find(r-1,c) + self.find(r+1,c) + self.find(r,c-1) + self.find(r,c+1)
            else:
                return 0
    
    def movingCount(self, threshold, rows, cols):
        self.rows = rows
        self.cols = cols
        self.threshold = threshold
        self.logs = [False]*(self.rows*self.cols) # 记载已经找到的格子
        return self.find(0, 0)