解決python迷宮問題的算法

本篇內容主要講解“解決python迷宮問題的算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“解決python迷宮問題的算法”吧!

一、迷宮介紹

用python解迷宮問題，迷宮是一個二維列表，本次用深度優先解開迷宮問題。定義起點和終點，從一個位置到下一個位置只能通過向上或下或左或右，走一步來實現，從起點出發，如何找到一條到達終點的通路。

二、深度優先遍歷

簡單那我們的案例來講就是，隨便選擇一條路，一直走，走不動了，再回頭重新選擇新的路

# 1 為墻，0 為路
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

首先我們先設置一個起點和終點

start = (1, 1)
end = (8, 8)

判斷當前這個點，0就是路可以走，1為墻不能走
對于一個點的下一個點的坐標準說明：

• 上走：r - 1, c

• 下走：r + 1, c

• 左走：r, c - 1

• 右走：r, c + 1
  

那我們這個迷宮的某個一個點達到了不能走的地步了，就是死胡同了，它就得原路返回

這時我們就有一個概念，就是棧，棧的思想就是：先進后出

怎么理解呢，可以舉一個小例子，就是食堂阿姨，每天早上蒸包子，他是一層一層放蒸籠
那放到最后，學生來吃包子，她是從上往往外拿，最上面就是最后放的，最下面是最先放的，所以就叫做先進后出

其實list就是一個棧，比如我們放一個空列表，然后我們用這個列表直接append

再用pop進行取出，就會取到append的最后一個元素

# 定義列表，列表里面放的就是每一步走的坐標，[r, c]
# 第一步就是起始位置，也就是start
list01 = [start]

走過的路定義為2

row, col = now
# python 里的解構也叫解包 now包括兩個位置，一個行，一個列
maze[row][col] = 2
# 這個代表就是走過的點，為2，因為你走過的路是不能再走的，除了走不通返回的時候，也是為了走不通按原來走過的路原路返回

核心代碼：

if maze[row - 1][col] == 0:
    # 上方可以走
    list01.append((row - 1, col))
    continue
elif maze[row][col + 1] == 0:
    # 右方可以走
    list01.append((row, col + 1))
    continue
elif maze[row + 1][col] == 0:
    # 下方可以走
    list01.append((row + 1, col))
    continue
elif maze[row][col - 1] == 0:
    # 左方可以走
    list01.append((row, col - 1))
    continue

最終代碼，可以運行一下試試：

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

start = (1, 1)
end = (8, 8)

# 定義列表，列表里面放的就是每一步走的坐標，[r, c]
# 第一步就是起始位置，也就是start
list01 = [start]

# 定義循環，讓它走
# 列表里最后存的就是下一步走的地方，當前列表有東西才能繼續走
while list01:
    # 當前走到的節點是哪一個節點，也就是最后走的一步，是哪一步，去列表的最后的一個值就是索引-1
    now = list01[-1]
    if now == end:  # 如果現在的now等于我們之前定義的終點end
        print(list01)
        print("出來了")
        break
    row, col = now
    # python 里的解構也叫解包 now包括兩個位置，一個行，一個列
    maze[row][col] = 2
    # 這個代表就是走過的點，為2，因為你走過的路是不能再走的，除了走不通返回的時候，也就是為了走不通按原來走過的路原路返回

	# continue 結束本次循環，從新開始判斷走路
    if maze[row - 1][col] == 0:
        # 上方可以走
        list01.append((row - 1, col))
        continue
    elif maze[row][col + 1] == 0:
        # 右方可以走
        list01.append((row, col + 1))
        continue
    elif maze[row + 1][col] == 0:
        # 下方可以走
        list01.append((row + 1, col))
        continue
    elif maze[row][col - 1] == 0:
        # 左方可以走
        list01.append((row, col - 1))
        continue
    else: # 走不通過，直接循環干掉每一步，重新調整路線
        list01.pop()

else:
    print("這個迷宮走不通")

到此，相信大家對“解決python迷宮問題的算法”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！