未加星标

python机器人行走步数问题的解决

字体大小 | |
[开发(python) 所属分类 开发(python) | 发布者 店小二05 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

本文实例为大家分享了python机器人行走步数问题,供大家参考,具体内容如下

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
# fileName : robot_path.py
# author : zoujiameng@aliyun.com.cn

# 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。
# 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
class Robot:
# 共用接口,判断是否超过K
def getDigitSum(self, num):
sumD = 0
while(num>0):
sumD+=num%10
num/=10
return int(sumD)

def PD_K(self, rows, cols, K):
sumK = self.getDigitSum(rows) + self.getDigitSum(cols)
if sumK > K:
return False
else:
return True

def PD_K1(self, i, j, k):
"确定该位置是否可以走,将复杂约束条件设定"
index = map(str,[i,j])
sum_ij = 0
for x in index:
for y in x:
sum_ij += int(y)
if sum_ij <= k:
return True
else:
return False

# 共用接口,打印遍历的visited二维list
def printMatrix(self, matrix, r, c):
print("cur location(", r, ",", c, ")")
for x in matrix:
for y in x:
print(y, end=' ')
print()

#回溯法
def hasPath(self, threshold, rows, cols):
visited = [ [0 for j in range(cols)] for i in range(rows) ]
count = 0
startx = 0
starty = 0
#print(threshold, rows, cols, visited)
visited = self.findPath(threshold, rows, cols, visited, startx, starty, -1, -1)
for x in visited:
for y in x:
if( y == 1):
count+=1
print(visited)
return count

def findPath(self, threshold, rows, cols, visited, curx, cury, prex, prey):
if 0 <= curx < rows and 0 <= cury < cols and self.PD_K1(curx, cury, threshold) and visited[curx][cury] != 1: # 判断当前点是否满足条件
visited[curx][cury] = 1
self.printMatrix(visited, curx, cury)
prex = curx
prey = cury
if cury+1 < cols and self.PD_K1(curx, cury+1, threshold) and visited[curx][cury+1] != 1: # east
visited[curx][cury+1] = 1
return self.findPath(threshold, rows, cols, visited, curx, cury+1, prex, prey)
elif cury-1 >= 0 and self.PD_K1(curx, cury-1, threshold) and visited[curx][cury-1] != 1: # west
visited[curx][cury-1] = 1
return self.findPath(threshold, rows, cols, visited, curx, cury-1, prex, prey)
elif curx+1 < rows and self.PD_K1(curx+1, cury, threshold) and visited[curx+1][cury] != 1: # sourth
visited[curx+1][cury] = 1
return self.findPath(threshold, rows, cols, visited, curx+1, cury, prex, prey)
elif 0 <= curx-1 and self.PD_K1(curx-1, cury, threshold) and visited[curx-1][cury] != 1: # north
visited[curx-1][cury] = 1
return self.findPath(threshold, rows, cols, visited, curx-1, cury, prex, prey)
else: # 返回上一层,此处有问题
return visited#self.findPath(threshold, rows, cols, visited, curx, cury, prex, prey)
#回溯法2
def movingCount(self, threshold, rows, cols):
visited = [ [0 for j in range(cols)] for i in range(rows) ]
print(visited)
count = self.movingCountCore(threshold, rows, cols, 0, 0, visited);
print(visited)
return count

def movingCountCore(self, threshold, rows, cols, row, col, visited):
cc = 0
if(self.check(threshold, rows, cols, row, col, visited)):
visited[row][col] = 1
cc = 1 + self.movingCountCore(threshold, rows, cols, row+1, col,visited) + self.movingCountCore(threshold, rows, cols, row, col+1, visited) + self.movingCountCore(threshold, rows, cols, row-1, col, visited) + self.movingCountCore(threshold, rows, cols, row, col-1, visited)
return cc

def check(self, threshold, rows, cols, row, col, visited):
if( 0 <= row < rows and 0 <= col < cols and (self.getDigitSum(row)+self.getDigitSum(col)) <= threshold and visited[row][col] != 1):
return True;
return False

# 暴力法,直接用当前坐标和K比较
def force(self, rows, cols, k):
count = 0
for i in range(rows):
for j in range(cols):
if self.PD_K(i, j, k):
count+=1
return count
# 暴力法2, 用递归法来做
def block(self, r, c, k):
s = sum(map(int, str(r)+str(c)))
return s>k
def con_visited(self, rows, cols):
visited = [ [0 for j in range(cols)] for i in range(rows) ]
return visited
def traval(self, r, c, rows, cols, k, visited):
if not (0<=r<rows and 0<=c<cols):
return
if visited[r][c] != 0 or self.block(r, c, k):
visited[r][c] = -1
return
visited[r][c] = 1
global acc
acc+=1
self.traval(r+1, c, rows, cols, k, visited)
self.traval(r, c+1, rows, cols, k, visited)
self.traval(r-1, c, rows, cols, k, visited)
self.traval(r, c-1, rows, cols, k, visited)
return acc

if __name__ == "__main__":
# 调用测试
m = 3
n = 3
k = 1
o = Robot()
print(o.hasPath(k, m, n))
print(o.force(m,n,k))
global acc
acc = 0
print(o.traval(0, 0, m, n, k, o.con_visited(m,n)))
print(o.movingCount(k, m, n))
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。
您可能感兴趣的文章:python开发的小球完全弹性碰撞游戏代码python计算书页码的统计数字问题实例python益智游戏计算汉诺塔问题示例Python使用遗传算法解决最大流问题浅谈Python实现贪心算法与活动安排问题Python3解决棋盘覆盖问题的方法示例Python基于回溯法解决01背包问题实例Python基于递归算法实现的走迷宫问题Python多线程经典问题之乘客做公交车算法实例Python基于动态规划算法解决01背包问题实例Python解决抛小球问题 求小球下落经历的距离之和示例

本文开发(python)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

tags: visited,self,cols,rows,threshold,curx,cury,return,lt,def,print
分页:12
转载请注明
本文标题:python机器人行走步数问题的解决
本站链接:http://www.codesec.net/view/572341.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(29)