python機(jī)器人行走步數(shù)問題的解決-創(chuàng)新互聯(lián)

本文實(shí)例為大家分享了python機(jī)器人行走步數(shù)問題，供大家參考，具體內(nèi)容如下

創(chuàng)新互聯(lián)建站網(wǎng)站建設(shè)公司是一家服務(wù)多年做網(wǎng)站建設(shè)策劃設(shè)計(jì)制作的公司,為廣大用戶提供了做網(wǎng)站、成都網(wǎng)站建設(shè)，成都網(wǎng)站設(shè)計(jì)，一元廣告，成都做網(wǎng)站選創(chuàng)新互聯(lián)建站，貼合企業(yè)需求，高性價(jià)比，滿足客戶不同層次的需求一站式服務(wù)歡迎致電。 
#! /usr/bin/env python3 
# -*- coding: utf-8 -*- 
# fileName ： robot_path.py 
# author : zoujiameng@aliyun.com.cn 
 
# 地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。  
# 例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18。但是，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19。請(qǐng)問該機(jī)器人能夠達(dá)到多少個(gè)格子？ 
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): 
    "確定該位置是否可以走,將復(fù)雜約束條件設(shè)定" 
    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: # 判斷當(dāng)前點(diǎn)是否滿足條件 
      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  
 
# 暴力法，直接用當(dāng)前坐標(biāo)和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__": 
  # 調(diào)用測(cè)試 
  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))

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享題目：python機(jī)器人行走步數(shù)問題的解決-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://muchs.cn/article18/idpgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、外貿(mào)網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化、響應(yīng)式網(wǎng)站、網(wǎng)站收錄、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

小程序開發(fā)