使用棧解決簡單迷宮

用二維列表模擬迷宮李根，1代表墻槽奕，0代表當前路是可以通過的
回溯法的核心是狀態(tài)的轉(zhuǎn)換房轿，當當前狀態(tài)不能進入下一狀態(tài)，我們就回溯到之前能進入下一狀態(tài)的某狀態(tài)結(jié)點夯接，我們用棧的append和pop去模擬這一過程

# 起始位置為(1, 1)  終點位置為(8, 8)
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

首先我們定義一個函數(shù)纷妆，函數(shù)的參數(shù)分別為起始位置和終點位置

def path(x1, y1, x2, y2):
    pass
path(1, 1, 8, 8)

我們定義當前狀態(tài)位置向四個方向轉(zhuǎn)移的函數(shù), 用python的λ函數(shù)來實習(xí)

directions = [
    lambda x, y: (x - 1, y),  # 上
    lambda x, y: (x + 1, y),  # 下
    lambda x, y: (x, y - 1),  # 左
    lambda x, y: (x, y + 1),  # 右
]

我們寫一個最簡易的框架, 定義一個棧把初始位置的元組放入棧，當棧不為空時候逊拍，不停尋找下一狀態(tài),當棧為空時际邻，說明當前迷宮是死路，我們設(shè)置終止狀態(tài)

def path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:
        # 當前狀態(tài)
        cur_node = stack[-1]
        # 終止狀態(tài)
        if cur_node[0] == x2 and cur_node[1] == y2:
            return True
            pass
    # 當棧為空時 說明為死路 走不到終點
    else:
        return False

接下來我們定義下一狀態(tài)next_node通過四個方向的函數(shù)不斷的判斷是否能通過如果四個方向皆不能滿足條件則利用stack的pop操作回溯到之前的某一能使條件滿足的狀態(tài)注整，為防止環(huán)路的出現(xiàn)，每次訪問過的路徑都設(shè)置為已訪問狀態(tài)肿轨。

 for direction in directions:
            # 下一狀態(tài)
            next_node = direction(cur_node[0], cur_node[1])
            if maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
                maze[next_node[0]][next_node[1]] = 2  # 把訪問過的路徑置為已訪問
                break     # 每成功一次就立刻進入下一次狀態(tài)的尋找
        # 如果四個方向皆不成立 回溯到之前的狀態(tài) 直到有條件滿足當前狀態(tài)
        else:
            # 利用棧的pop操作進行回溯
            stack.pop()
            maze[next_node[0]][next_node[1]] = 2

最終的代碼實現(xiàn)如下, 當滿足終止條件時蕊程，我們遍歷這個棧獲得詳細的路徑。

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

directions = [
    lambda x, y: (x - 1, y),  # 上
    lambda x, y: (x + 1, y),  # 下
    lambda x, y: (x, y - 1),  # 左
    lambda x, y: (x, y + 1),  # 右
]


def path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:
        # 當前狀態(tài)
        cur_node = stack[-1]
        if cur_node[0] == x2 and cur_node[1] == y2:
            for pat in stack:
                print(pat)
            return True
        print(stack)
        for direction in directions:
            # 下一狀態(tài)
            next_node = direction(cur_node[0], cur_node[1])
            if maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
                maze[next_node[0]][next_node[1]] = 2  # 把訪問過的路徑置為已訪問
                break     # 每成功一次就立刻進入下一次狀態(tài)的尋找
        # 如果四個方向皆不成立 回溯到之前的狀態(tài) 直到有條件滿足當前狀態(tài)
        else:
            # 利用棧的pop操作進行回溯
            stack.pop()
            maze[next_node[0]][next_node[1]] = 2
    # 當棧為空時 說明為死路 走不到終點
    else:
        return False
print(path(1, 1, 8, 8))

某一可達到終點的路徑

(1, 1)
(2, 1)
(1, 1)
(1, 2)
(2, 2)
(3, 2)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(5, 5)
(4, 5)
(4, 6)
(5, 6)
(5, 7)
(4, 7)
(3, 7)
(3, 8)
(4, 8)
(5, 8)
(6, 8)
(7, 8)
(8, 8)

可以通過打印棧的增長和減小過程來感受不停尋找下一狀態(tài)和回溯的過程

print(stack)
[(1, 1)]
[(1, 1), (2, 1)]
[(1, 1), (2, 1), (1, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (7, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (2, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (2, 8), (1, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (2, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8), (5, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8), (5, 8), (6, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8), (8, 8)]

最后編輯于：2023.04.03 18:52:16

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末优俘，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子帆焕，更是在濱河造成了極大的恐慌，老刑警劉巖财饥，帶你破解...
沈念sama閱讀 206,482評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件折晦，死亡現(xiàn)場離奇詭異，居然都是意外死亡满着，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,377評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門编饺，熙熙樓的掌柜王于貴愁眉苦臉地迎上來响驴，“玉大人，你說我怎么就攤上這事豁鲤【ň冢” “怎么了？”我有些...
開封第一講書人閱讀 152,762評論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵讼溺，是天一觀的道長。經(jīng)常有香客問我炫狱，道長，這世上最難降的妖魔是什么视译？我笑而不...
開封第一講書人閱讀 55,273評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任归敬，我火速辦了婚禮鄙早，結(jié)果婚禮上椅亚，老公的妹妹穿的比我還像新娘。我一直安慰自己呀舔，他們只是感情好，可當我...
茶點故事閱讀 64,289評論 5贊 373
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布躯舔。她就那樣靜靜地躺著省古，像睡著了一般粥庄。火紅的嫁衣襯著肌膚如雪豺妓。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,046評論 1贊 285
城市分裂傳說
那天训堆，我揣著相機與錄音白嘁，去河邊找鬼坑鱼。笑死絮缅，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的耕魄。我是一名探鬼主播，決...
沈念sama閱讀 38,351評論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼允扇，長吁一口氣：“原來是場噩夢啊……” “哼则奥！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起逞度，我...
開封第一講書人閱讀 36,988評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎俊戳，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體抑胎，經(jīng)...
沈念sama閱讀 43,476評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 35,948評論 2贊 324
?白月光啟示錄
正文我和宋清朗相戀三年铭拧，在試婚紗的時候發(fā)現(xiàn)自己被綠了恃锉。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 38,064評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡破托，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出州既，到底是詐尸還是另有隱情，我是刑警寧澤吴叶，帶...
沈念sama閱讀 33,712評論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布序臂，位于F島的核電站，受9級特大地震影響奥秆，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜吭练，卻給世界環(huán)境...
茶點故事閱讀 39,261評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一析显、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧分尸，春花似錦、人聲如沸箩绍。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,264評論 0贊 19
一樁弒父案圆到，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至芽淡，卻和暖如春豆赏，著一層夾襖步出監(jiān)牢的瞬間挣菲，已是汗流浹背掷邦。一陣腳步聲響...
開封第一講書人閱讀 31,486評論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留或杠，地道東北人。一個月前我還...
沈念sama閱讀 45,511評論 2贊 354
代替公主和親
正文我出身青樓廷痘，卻偏偏與公主長得像件已，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子篷扩，可洞房花燭夜當晚...
茶點故事閱讀 42,802評論 2贊 345

使用棧解決簡單迷宮

推薦閱讀更多精彩內(nèi)容