剑指offer全集详解python版——机器人的运动范围

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

思路: 【剑指offer全集详解python版——机器人的运动范围】回溯,开空间记录访问与否。
代码:

# -*- coding:utf-8 -*- class Solution: def movingCount(self, threshold, rows, cols): # write code here flag = [] for i in range(rows): flag.append([0] * cols) def DFS(start, rows, cols): if flag[start[0]][start[1]] != 1: if self.sumNumber(start[0], start[1])<= threshold: flag[start[0]][start[1]] = 1 if start[0]+1=0 : DFS([start[0]-1, start[1]], rows, cols) if start[1]+1 < cols: DFS([start[0], start[1]+1], rows, cols) if start[1]-1>=0: DFS([start[0], start[1]-1], rows, cols) else: flag[start[0]][start[1]] = -1 DFS([0,0], rows, cols) count = 0 for i in range(rows): for j in range(cols): if flag[i][j] == 1: count += 1 return count def sumNumber(self, rows, cols): r = str(rows) c = str(cols) count = 0 for i in r: count += int(i) for j in c: count += int(j) print(count) return count

    推荐阅读