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

作者:zoujm-hust12 时间:2023-12-24 23:26:05 

本文实例为大家分享了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))

来源:http://blog.csdn.net/shentong1/article/details/78775719

标签:python,机器人
0
投稿

猜你喜欢

  • Python编程利用Numpy和PIL库将图片转化为手绘

    2021-09-02 07:28:55
  • PHP cookie,session的使用与用户自动登录功能实现方法分析

    2023-11-21 15:00:43
  • asp随机生成文件名的函数

    2009-02-11 13:41:00
  • Python简单读写Xls格式文档的方法示例

    2021-11-02 13:27:30
  • 常用SQL功能语句

    2024-01-15 17:08:58
  • 浅谈Python中的生成器和迭代器

    2023-04-08 02:23:46
  • Python获取时光网电影数据的实例代码

    2023-10-22 21:40:52
  • Python查找算法之分块查找算法的实现

    2023-06-26 20:25:34
  • 基于keras中的回调函数用法说明

    2023-06-01 14:27:48
  • C#使用DataSet Datatable更新数据库的三种实现方法

    2024-01-13 23:38:20
  • Python3 操作符重载方法示例

    2021-03-18 11:38:03
  • vue实现商城秒杀倒计时功能

    2024-05-29 22:24:16
  • Python实现Word文档样式批量处理

    2022-01-13 01:16:05
  • Java连接MYSQL数据库的实现步骤

    2024-01-24 01:23:33
  • 原生js拖拽实现图形伸缩效果

    2024-04-16 08:55:27
  • MySQL 搭建MHA架构部署的步骤

    2024-01-17 05:27:10
  • 使用matplotlib库实现图形局部数据放大显示的实践

    2021-01-13 18:47:13
  • 细化解析:SQL Server数据库的集群设计

    2009-02-05 15:59:00
  • 利用Python编写一个简单的缓存系统

    2021-08-15 02:55:39
  • asp.net 防止用户通过后退按钮重复提交表单

    2023-07-21 00:03:54
  • asp之家 网络编程 m.aspxhome.com