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

題目描述：

最短路徑為：

uurrDDDDuuuulldRurDDDrddLLrruLuuulldRurDDDrdL

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

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

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

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

代碼：

# -*- 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)進入隊列(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<self.col and ny>=0 and ny<self.col):          continue        # python中字符串不可更改，于是把字符串變成list更改狀態(tài)后再轉(zhuǎn)換為字符串        if sta[pos] == '2' and sta[npos] == '0' and self.en[npos] != '1':        # 人和箱子一起推動，sta中連著的狀態(tài)為4 2 0，en中第三個不能為1。推完之后sta變?yōu)? 4 2          digits = [int(x) for x in sta]          digits[ppos],digits[pos],digits[npos] = 0,4,2          new_sta = ''.join(str(x) for x in digits)          if new_sta not in visi:            visi[new_sta] = 1            states.append([new_sta, path+dir[3], cx, cy])        elif sta[pos] == '0' and self.en[pos] !='1':        # 人動箱子不動，sta中連著的狀態(tài)為4 0，en中第二個不能為1。          digits = [int(x) for x in sta]          digits[ppos], digits[pos] = 0, 4          new_sta = ''.join(str(x) for x in digits)          if new_sta not in visi:            visi[new_sta] = 1            states.append([new_sta, path + dir[2], cx, cy]) if __name__ == '__main__':  f = open(level_file_path, encoding='utf-8')  cnt = 0  while(1):    line = f.readline()    line = line.strip('/n')    if len(line)==0 :      break    gs = GameShortest(line) """level_file.txt中內(nèi)容:11111111111111111111111000111111102211111114201111111110011111113001111113300111111111111111111111111111111111104000000110000200111001101011100100101110010010111001011001110030000111111111111111111111111111111111111111111111111111111031111114002000111023002011111131111111111111111111111111111111111111111111111111111111111000111111102211111110133111111023011111100401111111111111111111111111111111111111111111111111111111111111111100000111112111001113030020111400100011111111111111111111111111111111111111111111111111111111111111111001111110000001111100122011114030031111111111111111111111111111111111111111111100400011100000001110011100111100110011110201301111000020111113111111111111111111111111111111111111111111111111111111111100111111100320001110131210111000000411111111111111111111111111111111111111111111111111111111111111110000011110011101111000202011100013341111111111111111111111111111111111111111111111111111111001111111100041111111010111113121001111320010111130002011111111111111111111111111111111111111111111000001111131103111110402011111001201111100100111111111111111111111111111111111111111111111111111111110000111111311201111023400111100100011110000111111111111111111111111111111111111111111111111111111111110011111102041111110200111113001011111300001111111111111111111111111111111111111111111111111111111143001111100000111110010211111001203111111101011111110001111111111111111111111111111111111111111111111111111110000111111020211111103342011111113001111111111111111111111111111111111111111111111111111111100011111002301111140323011111101201111110001111111111111111111111111111111111111111111111111111111110031111102010111110020011111031401111100001111111111111111111111111111111111111111111111111111111111110411111311001111033020111102120011110000111111111111111111111111111111111111111111111111111111110001111111003301111100112111111001001111120004111110011111111111111111111111111111111111111111111111100001111103032111110024001111111010111111100011111111111111111111111111111111每一關(guān)的最短路徑:['uurrDDDDuuuulldRurDDDrddLLrruLuuulldRurDDDrdL']['drrRRurDDDDDrdLLL']['rrdrUrrrdLLulDullldR']['lluRRdrUllluuurrDDuulldRurD']['urrrrdrruulullllDurrrrdrddllullLrrrdrruLLL']['uurrrrDulllddrrRuulDrdL']['drrdddrdLLLuLDlUUUluRRRRurDDD']['uullLLddrrUdlllluuRurDrRddrruuLLL']['lUlLLdlluururrrrDDrdLullldlluRRRRllluurrrrdD']['ddrddLLulLdlUrrrdrruuluulldDuurrddrddllLLrruLL']['luurrrdrdLLLrrrddlUruuulllldDrddlUUrrRdrU']['ddlluluRuurrrDrddlluLrdrruLLddlluU']['dddlluluuRDrruulDrdLLulDrDLurrrddlLL']['drrdDrrddllUUUUruLdrDldR', 'drrdDrrddllUUUUrDldRuuuL']['drruLLLuulldRurDurDD']['urRdddrrUULLulldRururrD']['uLrddlluluuRDrrruullDldRRdrUU']['dddlUllllddrUUddrrUruLLrrruulDrdLL']['llldlUUUluurDrrrDDrdLLLulUluRRlddrddlUUUluR']['ulldRurDrrddllUUluurrDLLdrddrruuLrddlluU']"""