题目描述:
地上有一个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
推荐阅读
- 人工智能|干货!人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点(详细介绍 Python 中的 7 种交叉验证方法!)
- 网络|简单聊聊压缩网络