[剑指Offer]机器人的运动范围

题目描述

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

解题思路

[剑指Offer]矩阵中的路径类似,采用回溯法来解题。额外生成一个布尔矩阵,用来存放该位置是否已经被遍历过。只不过判断条件有三个:

  1. 坐标是否超出边界;
  2. 坐标之和是否大于给定阈值;
  3. 该位置是否被遍历过

对于不满足上述条件的位置,计数器返回0;对于所有满足上述条件的位置,计数器为1+周围四个位置的返回值(周围的不合法位置返回为0,所以不会影响)。

代码

Python(2.7.3)

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

def moveingCount2(self, threshold, rows, cols, i, j, visited):
count = 0
if i >= 0 and i < rows and j >= 0 and j < cols and self.add(i) + self.add(j) <= threshold and not visited[i * cols + j]:
visited[i * cols + j] = True
count = 1 + self.moveingCount2(threshold, rows, cols, i - 1, j, visited) + self.moveingCount2(threshold, rows, cols, i + 1, j, visited) + self.moveingCount2(threshold, rows, cols, i, j - 1, visited) + self.moveingCount2(threshold, rows, cols, i, j + 1, visited)
return count

def add(self, n):
num = 0
while n:
num += n % 10
n //= 10
return num

运行时间:27ms
占用内存:5736k