一道python走迷宮算法題

更新時(shí)間：2018年01月22日 10:44:44 作者：sinly100

這篇文章主要為大家詳細(xì)介紹了一道python走迷宮算法題，用一個(gè)二維數(shù)組表示一個(gè)簡(jiǎn)單的迷宮，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

前幾天逛博客時(shí)看到了這樣一道問題，感覺比較有趣，就自己思考了下方案順便用python實(shí)現(xiàn)了一下。題目如下：

用一個(gè)二維數(shù)組表示一個(gè)簡(jiǎn)單的迷宮，用0表示通路，用1表示阻斷，老鼠在每個(gè)點(diǎn)上可以移動(dòng)相鄰的東南西北四個(gè)點(diǎn)，設(shè)計(jì)一個(gè)算法，模擬老鼠走迷宮，找到從入口到出口的一條路徑。

如圖所示：

先說下我的思路吧：

1、首先用一個(gè)列表source存儲(chǔ)迷宮圖，一個(gè)列表route_stack存儲(chǔ)路線圖，一個(gè)列表route_history存儲(chǔ)走過的點(diǎn)，起點(diǎn)（0,0），終點(diǎn)（4,4）。

2、老鼠在每個(gè)點(diǎn)都有上下左右四種方案可選，需要定義這些方案的執(zhí)行方法。

3、最后做一個(gè)循環(huán)，如果當(dāng)前點(diǎn)不是（4,4）的話就依次執(zhí)行上下左右四種方法，但是有些限制，比如嘗試走過的點(diǎn)不會(huì)再嘗試走，（0，x）點(diǎn)無法再執(zhí)行向上的方法等等。

貼一下代碼：

# _*_ coding:utf-8 _*_  
route_stack = [[0,0]] 
route_history = [[0,0]] 
source=[[0,0,1,0,1],[1,0,0,0,1],[0,0,1,1,0],[0,1,0,0,0],[0,0,0,1,0]] 
def up(location): 
  #橫坐標(biāo)為0，無法再向上走 
  if location[1] == 0: 
    return False 
  else: 
    new_location = [location[0],location[1]-1] 
    #已經(jīng)嘗試過的點(diǎn)不會(huì)嘗試第二次 
    if new_location in route_history: 
      return False 
    #碰到墻不走 
    elif source[new_location[0]][new_location[1]] == 1: 
      return False 
    else: 
      route_stack.append(new_location) 
      route_history.append(new_location) 
      return True 
 
def down(location): 
  if location[1] == 4: 
    return False 
  else: 
    new_location = [location[0],location[1]+1] 
    if new_location in route_history: 
      return False 
    elif source[new_location[0]][new_location[1]] == 1: 
      return False 
    else: 
      route_stack.append(new_location) 
      route_history.append(new_location) 
      return True 
 
def left(location): 
  if location[0] == 0: 
    return False 
  else: 
    new_location = [location[0]-1,location[1]] 
    if new_location in route_history: 
      return False 
    elif source[new_location[0]][new_location[1]] == 1: 
      return False 
    else: 
      route_stack.append(new_location) 
      route_history.append(new_location) 
      return True 
 
def right(location): 
  if location[0] == 4: 
    return False 
  else: 
    new_location = [location[0]+1,location[1]] 
    if new_location in route_history: 
      return False 
    elif source[new_location[0]][new_location[1]] == 1: 
      return False 
    else: 
      route_stack.append(new_location) 
      route_history.append(new_location) 
      return True 
lo = [0,0] 
while route_stack[-1] != [4,4]: 
  if up(lo): 
    lo = route_stack[-1] 
    continue 
  if down(lo): 
    lo = route_stack[-1] 
    continue 
  if left(lo): 
    lo = route_stack[-1] 
    continue 
  if right(lo): 
    lo = route_stack[-1] 
    continue 
  route_stack.pop() 
  lo = route_stack[-1] 
print route_stack

執(zhí)行結(jié)果如下：