python如何解決走迷宮算法題

這篇文章將為大家詳細講解有關python如何解決走迷宮算法題，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

用一個二維數組表示一個簡單的迷宮，用0表示通路，用1表示阻斷，老鼠在每個點上可以移動相鄰的東南西北四個點，設計一個算法，模擬老鼠走迷宮，找到從入口到出口的一條路徑。

如圖所示：

先說下我的思路吧：

1、首先用一個列表source存儲迷宮圖，一個列表route_stack存儲路線圖，一個列表route_history存儲走過的點，起點（0,0），終點（4,4）。

2、老鼠在每個點都有上下左右四種方案可選，需要定義這些方案的執行方法。

3、最后做一個循環，如果當前點不是（4,4）的話就依次執行上下左右四種方法，但是有些限制，比如嘗試走過的點不會再嘗試走，（0，x）點無法再執行向上的方法等等。

貼一下代碼：

# _*_ 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): 
  #橫坐標為0，無法再向上走 
  if location[1] == 0: 
    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 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

執行結果如下：

題目出處有另一種解題思路，但是我覺得有點煩，自己的這個比較好理解點，實現起來也比較方便。

關于“python如何解決走迷宮算法題”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。