本文實例為大家分享了python實現(xiàn)推箱子游戲的具體代碼，供大家參考，具體內(nèi)容如下

網(wǎng)站建設(shè)公司,為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁設(shè)計及定制網(wǎng)站建設(shè)服務(wù),專注于成都企業(yè)網(wǎng)站定制,高端網(wǎng)頁制作,對成都宣傳片制作等多個行業(yè)擁有豐富的網(wǎng)站建設(shè)經(jīng)驗的網(wǎng)站建設(shè)公司。專業(yè)網(wǎng)站設(shè)計,網(wǎng)站優(yōu)化推廣哪家好,專業(yè)seo優(yōu)化排名優(yōu)化,H5建站,響應(yīng)式網(wǎng)站。

題目描述：

最短路徑為：

uurrDDDDuuuulldRurDDDrddLLrruLuuulldRurDDDrdL

u表示向上，d表示向下，l表示向左，r表示向右。

大寫表示人推著箱子一起動，小寫表示人自己走。

代碼用BFS實現(xiàn)。狀態(tài)要分推著箱子一起走和人單獨走，這兩種狀態(tài)轉(zhuǎn)移是不同的。

由于代碼中注釋較詳細(xì)，這里不過多解釋。

代碼：

# -*- coding: utf-8 -*-
# @Time : 2017/8/10 上午9:42
# @Author : Qi MO
# @File : BFS.py
# @Software: PyCharm Community Edition
 
level_file_path = '../數(shù)據(jù)/level_file.txt'
 
class GameShortest:
 def __init__(self,line, col=10):
  """
  給一個圖，長度為100的字符串表示。
  0空地 1墻 2箱子起始位置 3箱子終點位置 4人的起始位置
  :param line: 地圖，用字符串表示。如代碼最后的每一行表示每一關(guān)的地圖。
  :param col: 地圖的長寬，由于設(shè)定為10*10，默認(rèn)為10
  """
 
  self.line = line
  # sta和en 表示開始的狀態(tài)，結(jié)束的狀態(tài)
  # sta只有2,4,0 2表示箱子開始位置,4表示人的位置,0表示其他。
  # en只有1,3,0 1表示墻,3表示箱子結(jié)束位置,0表示其他。
  # 現(xiàn)在只需要把sta狀態(tài)中的2位置移動到en的3的位置即滿足條件
  self.sta = ''
  self.en = ''
  self.col = col
  # px, py表示4的位置
  self.px,self.py = -1,-1
  # paths記錄最短路徑（可能有多條）
  self.paths = []
  # len記錄最短路徑長度 如
  self.len = -1
 
  self.pre()
  self.BFS()
  print(self.paths)
 
 def pre(self):
  """
  1.獲得sta開始狀態(tài)和en結(jié)束狀態(tài)
  2.獲得人的起始位置px,py
  代碼最后的第一關(guān)的地圖可視化為
  1111111111
  1111111111
  1110001111
  1110221111
  1114201111
  1111100111
  1111300111
  1113300111
  1111111111
  1111111111
  :return:
  """
  mp = []
  for pos in range(0, 100, 10):
   mp.append(self.line[pos:pos + 10])
  # print(self.line)
  # for x in mp:
  #  print(x)
 
  for pos, enum in enumerate(self.line):
   cx, cy = pos // 10, pos % 10
   if enum == '4':
    self.px, self.py = cx, cy
  # 現(xiàn)在只需要把sta開始的狀態(tài)中的2位置移動到en的3的位置即滿足條件
  staDic = {'0': '0', '1': '0', '2': '2', '3': '0', '4': '4'}
  enDic = {'0': '0', '1': '1', '2': '0', '3': '3', '4': '0'}
  for x in self.line:
   self.sta += staDic[x]
   self.en += enDic[x]
  # print(self.sta)
  # print(self.en)
 
 def is_ok(self,sta):
  """
  sta狀態(tài)中的2位置移動到en的3的位置。
  :param sta:
  :return:
  """
  for s,e in zip(sta,self.en):
   if e == '3' and s != '2':
    return False
  return True
 
 def BFS(self):
  """
  BFS獲得最短路徑保存到paths中
  :return:
  """
  # 4個方向，小寫代表只是人移動，大寫表示人推著箱子一起移動
  dirs = [[-1,0,'u','U'],[1,0,'d','D'],[0,1,'r','R'],[0,-1,'l','L']]
  # 把開始的狀態(tài)進(jìn)入隊列(list模擬)，狀態(tài)包括字符串表示的當(dāng)前狀態(tài)、當(dāng)前的路徑、當(dāng)前人的位置
  states = [[self.sta,'',self.px,self.py]]
  # 訪問數(shù)組(dict模擬)，訪問過的狀態(tài)（字符串）不再訪問
  visi = {}
  visi[self.sta] = 1
 
  s_len = 1000
  while len(states)>0:
   sta, path, px, py = states[0]
   # 4狀態(tài)的位置
   ppos = px*self.col + py
   states = states[1:]
   if len(path)>s_len:
    break
   # 保存最短路徑到paths中
   if self.is_ok(sta):
    if self.len == -1 or len(path) == self.len:
     self.paths.append(path)
     self.len = len(path)
    continue
 
   for dir in dirs:
    cx, cy = px + dir[0], py + dir[1]
    # 4挨著的狀態(tài)的位置
    pos = cx*self.col+cy
    nx, ny = px + 2*dir[0], py + 2*dir[1]
    # 4挨著挨著的狀態(tài)的位置
    npos = nx*self.col+ny
    if not (nx>=0 and nx=0 and ny            

            當(dāng)前名稱：python實現(xiàn)推箱子游戲-創(chuàng)新互聯(lián)            

            文章出自：http://weahome.cn/article/eiidj.html