python机器人运动范围问题的解答

yipeiwu_com7年前Python基础

机器人的运动范围Python实现:

问题:地上有个 m 行 n 列的方格。一个机器人从坐标(0,0)的格子开始移动,它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于 k 的格子。

例如,当 k 为 18 时,机器人能够进入方格(35,37),因为 3+5+3+7=18 但它不能进入方格(35,38),因为 3+5+3+8=19 请问该机器人能够达到多少格子?

回溯算法。

当准备进入坐标(i,j)时,通过检查坐标的数位来判断机器人能否进入。如果能进入的话,接着判断四个相邻的格子。

代码:

# -*- coding:utf-8 -*-
class Solution:
 def movingCount(self, threshold, rows, cols):
  # write code here
  matrix = [[True for i in range(cols)] for j in range(rows)]
  result = self.findgrid(threshold, rows, cols, matrix, 0, 0)
  return result
 
 def judge(self, threshold, i, j):
  if sum(map(int,str(i)+str(j))) <= threshold:
   return True
  else:
   return False
  
 def findgrid(self, threshold, rows, cols, matrix, i, j):
  count = 0
  if i < rows and i>=0 and j<cols and j>=0 and self.judge(threshold, i, j) and matrix[i][j]:
   matrix[i][j] = False
   count = 1+ self.findgrid(threshold, rows, cols, matrix, i-1, j) \
     + self.findgrid(threshold, rows, cols, matrix, i+1, j) \
     + self.findgrid(threshold, rows, cols, matrix, i, j-1) \
     + self.findgrid(threshold, rows, cols, matrix, i, j+1)
  return count

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

python实现自动化报表功能(Oracle/plsql/Excel/多线程)

python实现自动化报表功能(Oracle/plsql/Excel/多线程)

日常会有很多固定报表需要手动更新,本文将利用python实现多线程运行oracle代码,并利用xlwings包和numpy包将结果写入到指定excel模版(不改变模版内容),并自动生成带...

Python Sympy计算梯度、散度和旋度的实例

sympy有个vector 模块,里面提供了求解标量场、向量场的梯度、散度、旋度等计算,官方参考连接: http://docs.sympy.org/latest/modules/vect...

Python列表对象实现原理详解

Python列表对象实现原理详解

Python中的列表基于PyListObject实现,列表支持元素的插入、删除、更新操作,因此PyListObject是一个变长对象(列表的长度随着元素的增加和删除而变长和变短),同时它...

python创建学生管理系统

python创建学生管理系统

使用python创建学生管理系统,供大家参考,具体内容如下 创建学生管理系统,可谓是学习编程最基础的一小步。 主要是分为以下几个思路: 接下来直接上源码 #!/usr/bin/py...

Python中函数参数设置及使用的学习笔记

Python中函数参数设置及使用的学习笔记

一、参数和共享引用: In [56]: def changer(a,b): ....: a=2 ....: b[0]='spam' ....: In [57...