一個迷宮從入口進去，沿著右手邊的牆走，是否肯定能走到出口？

12-16

如題，前提是迷宮是一層的。或者說就是平時報紙雜誌上那種。是否能設計出反例？

小時候沒有什麼玩的，經常做迷宮給別人玩兒，有一天我發現只要沿著一邊走就一定可以找到出口，因為每次畫迷宮都是先畫一個長方形，標上入口和出口，然後在長方形的邊上進行延展，這樣一來其實每次走迷宮都只是在原先長方形四條邊的延伸上面行走而已，所以一定會環繞長方形走完：

迷宮經過 收線、拉直 兩步操作，最後會變成兩條線，只要沿著一邊走就一定能找到出口。。。

製作迷宮的事情受到了很大打擊，因為你提出了一個難題，但是別人分分鐘搞定，這樣的挫敗感真的很強。
所以我發揮聰明才智，製作出了多層迷宮這種東西：

以上是原理圖，可惜世界上玩過我親手製作的多層迷宮的人不超過10個，因為做一個太麻煩了。。。

把多層迷宮進行 收線、拉直 兩步操作，最後會變成大概這個樣子：

因為多層迷宮間上下聯通的關係，很容易出現循環、嵌套、聯通的情況，本來你一直在往左走，走著走著走到了右面。。。
所以如果製作複雜的多層迷宮，只要圈圈套圈圈，循環又循環，就可以把迷宮變得很複雜。

多層迷宮製作完成後，我對自己的成果非常滿意，因為我覺得我發現了一個複雜事物的簡單原理。

只是從此以後，再也沒有畫迷宮玩過了，就像九連環、孔明鎖、魔方一樣，曾經覺得有意思的事情，一旦知道了玩法，就再也不會去動它了。。。

按照果殼網的說法：

首先就是「左/右手法則」方法。顧名思義，就是進入迷宮後，選擇一個方向，之後貼著牆壁一直走下去。這是最常見的走迷宮方法，其原理其實在上面「克里特式迷宮」中也已提到，就在於考察迷宮的拓撲結構，無論圍牆是多麼的蜿蜒曲折，把它抻直了也就是一根線段而已，迷宮的出入口分別對應著這條線段的兩個端點。我們從入口進（或者選擇該條線段上任意一點開始），沿著這條線筆直走下去，當然會走到出口。但這個法則也時常有失靈的時候。因為它的前提是「入口和出口都在一條線段上」，也就是說這堵牆必須是連通的才行，而如果遇到「回字形」迷宮，出口和入口並不連通，則會出現繞了一圈返回原地的情況

用迷宮困住死理性派？沒門！

對於這種迷宮，題主的方法是一定可行的。

（圖片來自百度搜索）
要求有兩個：
第一，迷宮是一個有外牆的矩形，並且僅有一個出口，一個入口。
第二，迷宮至少要有一個解。

以上圖為例做一下說明。首先把牆想像成一個個氣球或者是氣泡，牆的邊界肯定是一個一個的圈，彼此肯定不會相交。第一個要求保證了這一點。
考慮入口處的A點和出口處的B點

因為第二個要求，解一定至少存在一個。因此整個圖裡面牆一定不止一片。用拓撲的話來說，牆的連通分支一定不只一個。因為解是從入口到出口的，所以外牆不會在同一個分支里。如下圖，外牆上一定有黑色的部分。
而A和B一定在同一個連通分支裡面，因為A和B能通過邊框上的牆連接起來。我們可以在這個圖中把這一片牆標出來，就是藍色的部分。第二個要求保證了藍色部分一定不是全部。

注意一點，拓撲上來講，藍色的這一片不一定同胚於D^2的，因為可能中間是有洞的，但是沒關係，我們關心的是她的各個邊界中的其中一個。事實上，我們已經找到了一半的邊界，也就是迷宮的外牆。如下圖的紅線

而前面已經說了，每一條邊界一定是一個封閉曲線，因此我們一定可以把上面的紅線補成一段完整的曲線。補出來的那一部分一定全部落在迷宮裡面，若不然，那麼就會跑到黑色的部分去了，但是藍色和黑色不是同一個分支，這是不可能的。
也就是說，紅線的另外一半恰好全部落在迷宮內部，這就是迷宮的解了。
因為這一半是牆的邊界，因此沿著她走的時候一定是可以扶牆的。而扶牆的時候不用換手，這是藍色部分的牆可定向保證的。由於一開始是右手扶著進去，因此就一直是右手扶牆了。以上。

大概想了下，總是可以走出去的，因為每一堵牆你都可以把它縮成是一個類似圓盤的東西，邊界是一個連通的圓。因為是在入口處的牆，所以這個圓一定有一段在迷宮外，因為是連通的，所以你一定可以沿著圓走到這一段。

對於有一個出口，一個入口，二者連通且均在外邊界上的二維迷宮來講，是的。

我們從入口進去，沿著右手不停地走，總共有三種可能的結果：1. 從出口離開； 2. 在某一特定迷宮結構內死循環； 3. 從入口離開。

首先，結果2是不可能的。如果我們始終沿右手邊界走，那麼一個死循環結構必然是一個閉合的圈，但是既然我們可以進入到這個結構，那麼它就必須是有入口的，（就像進去迷宮要有入口），這個入口就是一個缺口，這就保證了這種閉合圈是不可能存在的，因此不可能有死循環存在。

其次，結果3也是不可能的。如果我們沿右手走一圈又回到出口，那麼這個路徑本身加上迷宮入口就一定是一個閉合的圈，同時迷宮出口一定在圈外（因為它在外邊界上），但由於這個圈是閉合的，所以不存在一條可以通到圈外的路徑，所以這隻能說明這個迷宮本身就不存在一條通路，與假設矛盾，故不可能。

故，必然可以走出去。

不知道這個能不能算特殊情況。不算的話，靠右邊走一定能走到出口，沒有任何疑問。

關鍵詞：計算機專業，演算法，深度優先搜索

之前的回答有問題，修改了下：

這個問題對應的演算法中圖的深度優先搜索分析如下：

首先，迷宮的定義是什麼？可能是圖結構，可能是樹結構。

圖結構迷宮：迷宮中每個岔路點視為圖的結點。靠右走的實質相當於遇到每個結點時，下級結點分支優先順序為：右前左。當一個分支走到盡頭，就是死路時，繼續靠右走相當於回到上級結點。但是圖結構可能有迴路，進入迴路繼續靠右走會死循環。圖的深度優先搜索方法要記錄之前走過的節點，以後不再重複走相同節點，防止進入迴路，但是「沿著右邊走」這個方法沒有記錄之前走過的節點。

樹結構迷宮：樹的定義是沒有迴路的圖，所以深度優先遍歷樹不需要記錄走過的節點，「沿著右邊走」這個方法可以找到出口葉子節點。（常說的迷宮其實都是樹結構，而且通常是二叉樹，因為每個結點都只有兩個分支，@王箏的那個迷宮例子就是二叉樹）

總結：樹結構迷宮，這個方法可解；圖結構迷宮，這個方法不可解，除非記錄之前走過的節點（其實要記錄也很容易）。

其實，這樣研究迷宮脫離了本質。什麼情況下你非走迷宮不可？

要想思考這個問題，想一下最近看過的電影「移動迷宮」。

你必須要走出迷宮的原因是你在迷宮之內，走出去（比方說密室逃脫）。或者你在迷宮之外，要到達迷宮內的某個地方（比方說逛商場）。這兩種情況下，都可以出現環路，使得靠牆法則無效。

@王箏所說的那種迷宮只有數學上的意義，在現實中很少有這種設計，除非「故意為了降低迷宮難度而設計出這種迷宮」。

@Tony Young 的迷宮屬於更典型的情況：你被打暈了扔進迷宮內，怎麼走出來？你可以說這是密室逃脫類問題，但它其實在迷宮設計中更廣泛。因為迷宮之所以成為迷，就一定要有內部迴路，內部能讓你走回路的迷宮，出口入口一定不在一面牆上。

當然，有很多人認為遊戲中的迷宮大多是靠一邊牆走能解決。這首先是為了避免難度過高，其次是為了讓你在迷宮內的時間可控，在迷宮內浪費過長時間有可能讓你刪遊戲不是么？

結論：如果起點終點在同一面牆上，當然可以靠牆走。但這樣的迷宮缺乏環路，除非是故意降低難度，否則不會這麼設計的。

2014.9.29
哎，更新下答案吧。有些評論實在是挺令人不悅。

紅色路徑代表沿入口處左右邊牆行走。
綠色路徑代表通向出口路徑。
圖匆忙間畫得，有些丑，見諒。

評論中提出此非單層迷宮，針對這點，題主始終未補充說明其所說的「層」的具體概念，網上也未找到有關迷宮「層」的相關定義。我傾向於認為題主所說的「層」是指迷宮位於單一平面，而非果殼網文章中所說的「單連通、多連通」，因為題主如之前看過此文，可能便不會在此發文。（猜測）

以上。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~分割線~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

很不幸, 這個結論是錯的.
但這個錯是有用的, 用處在最後.

----回憶殺----
記得那時小學三年級的樣子, 我在玩大名鼎鼎的&<新仙劍奇俠傳&>. 大家記得有個將軍冢嗎?
就是這個迷宮! 我走了整整三個小時!!! 一個下午的時間沒了!!!! 還沒走出來!!!!我靈兒都尼瑪會風雪冰天了!!! 錢多到看到怪就想乾坤一擲砸死他們!!(忍住了)
在那個沒有網路的年代, 真實讓我感到煩躁和絕望, 給我留下了巨大的心理陰影.

後來我靈機一動, 貼著右邊走不就行了嗎, 迷宮就兩個口, 肯定能出來! 我再次從入口出發, 帶著一股壓抑的興奮, 像準備發現新大陸一樣的心情. 最後終於見到那個腦殘大將軍, 三下五除二就幹掉了(包括後面的赤血王). 哈哈! 我像發現XX第一定律一樣高興, 為自己的智商感到深深的驕傲!

就這樣, 我憑藉迷宮第一定律, 在那個年代, 任何迷宮都攔不住我的腳步, 閉著眼睛都能走出去, 呵呵.

直到, 高二的時候, 玩那個迷宮----&<空之軌跡FC&>, 約修亞一行人從下水道潛入王宮的某一段下水道.

我像往常一樣藐視這個迷宮. 走走走, 打打打. 走走走, 打打打, 咦?怎麼會到入口了?不可能, 還沒看到出口呢. 走走走, 打打打, 咦?怎麼又到入口了, 是不是不小心走錯了? 走走走, 打打打, 我擦肯定是走錯了! 這次貼著左邊的牆走! 走走走, 打打打. 我擦又回來了, 怎麼會這樣?再試一試...

不知走了多少圈, 我都能背下一路的地圖了, 才意識到, 迷宮第一定律是不完美的, 三觀崩壞...

然後我發瘋地想為什麼會出錯! 想知道這個漏洞在哪裡! 想了很久才想明白----左邊的牆和右邊的牆是同一道牆! 一直在轉圈! 其實這迷宮就是"回"字型的, 入口在裡面的"口"上, 出口在外面的"口"上...

在這個年代, 別說這個結論是錯的, 哪怕是對的, 在各種奇葩機關的干擾下, 不會那麼容易能以一個標準去走通各種迷宮了.

----PS----
題主, 其實我想說, 別管這個結論是對是錯, 也別找其它很牛逼的走迷宮技巧, 認真走一下迷宮吧! 我感覺就是以前沒好好努力走迷宮, 搞的現在自己如此路痴 (╯‵□′)╯︵┻━┻

1.迷宮是一層的，或者說迷宮的出口和入口是可以從迷宮外連接的（上面說的回字形就不符合這個要求）；
2.迷宮是有解的。
只要上述兩個條件成立，那麼出口和入口一側的牆一定是同一堵牆，雖然是有很多彎的牆，但他始終是一個封閉多邊形（考慮牆的厚度），所以沿一邊走肯定能從多邊形任意頂點到另一頂點。

如圖，出口和入口由綠，紅兩堵牆連接，都構成了一個多邊形，所以，不論沿左邊還是沿右邊都可以從多邊形一個頂點走到另一個頂點

諸位認識它嗎？

從入口進去，貼牆走，一定能走到入口。
所以能否走到出口，也就等價於從出口貼牆（包括迷宮的外牆）能否走到入口。

簡單了吧？

你首先就限定了迷宮必須是有外牆的，必須是從最外層進入的，必須是最外層離開的。那有啥說的。限制條件太多了。

第一個圖的迷宮其實很常見，兩個有缺口的同心圓而已。就能破解你的想法。

出口放在迷宮中間

問這個問題的一看就是沒見過win98的屏保

二維迷宮，入口和出口必須都在外牆，這樣一定能走出來

如果是上圖這樣的迷宮（http://tools.dourok.info/mazegame/mazegame.html），我在迷宮生成演算法說過這樣的迷宮有兩個特點，

1. 它是一個連通圖，這個可以理解，迷宮裡到達不了的地方實際上沒有意義。
2. 沒有迴路，無論你從那個地方出發，只要不往回走，就永遠也回不到原來出發的地方，也就是不會繞圈圈。

那這樣的迷宮就是一顆樹，從迷宮入口進去，沿著右手邊的牆走，其實就是等同於深度優先搜索，這個演算法可以從根節點出發遍歷所有節點，那必然可以到達出口的節點。

當然不是所有迷宮都有這樣的特點，所以說了這麼多還是不能回答問題，如果一定要給個答案，那我說不是，畢竟迷宮是藝術創作，沒有什麼限制，只要加上迴路那這樣走法就有可能會不停繞圈圈。

要麼從出口出來，找到一個解。

要麼從入口出來，無解。

完全可以本人嘗試過進入迷宮一直右手貼牆走
PS 據說老鼠就是這樣走的