英文原文：Representing and solving a maze given an image
譯注：原文是 StackOverflow 上一個如何用程序讀取迷宮圖片并求解的問題，幾位參與者熱烈地討論并給出了自己的代碼，涉及到用 Python 對圖片的處理以及廣度優先(BFS)算法等。
問題 by Whymarrh：
當給定上面那樣一張 JPEG 圖片，如何才能更好地將這張圖轉換為合適的數據結構并且解出這個迷宮？
我的第一直覺是將這張圖按像素逐個讀入，并存儲在一個包含布爾類型元素的列表或數組中，其中 True 代表白色像素，False 代表非白色像素（或彩色可以被處理成二值圖像）。但是這種做法存在一個問題，那就是給定的圖片往往并不能完美的“像素化”。考慮到如果因為圖片轉換的原因，某個非預期的白色像素出現在迷宮的墻上，那么就可能會創造出一一條非預期的路徑。
經過思考之后，我想出了另一種方法：首先將圖片轉換為一個可縮放適量圖形(SVG)文件，這個文件由一個畫布上的矢量線條列表組成，矢量線條按照列表的順序讀取，讀取出的仍是布爾值：其中 True 表示墻，而 False 表示可通過的區域。但是這種方法如果無法保證圖像能夠做到百分之百的精確轉換，尤其是如果不能將墻完全準確的連接，那么這個迷宮就可能出現裂縫。
圖像轉換為 SVG 的另一個問題是，線條并不是完美的直線。因為 SVG 的線條是三次貝塞爾曲線，而使用整數索引的布爾值列表增加了曲線轉換的難度，迷宮線條上的所有點在曲線上都必須經過計算，但不一定能夠完美對應列表中的索引值。
假設以上方法的確可以實現(雖然很可能都不行)，但當給定一張很大的圖像時，它們還是不能勝任。那么是否存在一種更好地方法能夠平衡效率和復雜度？
這就要討論到如何解迷宮了。如果我使用以上兩種方法中的任意一種，我最終將會得到一個矩陣。而根據這個問答(http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze/3097677#3097677)，一個比較好的迷宮表示方式應該是使用樹的結構，并且使用A*搜索算法來解迷宮。那么如何從迷宮圖片中構造出迷宮樹呢？有比較好的方法么？
以上廢話太多，總結起來問題就是：如何轉換迷宮圖片？轉換成為什么樣的數據結構？采用什么樣的數據結構能夠幫助或阻礙解迷宮？
回答 by Mikhail:
這是我的解決方案：
1. 將圖片轉換為灰度圖像(不是直接二值)，調整不同顏色的權重使得最終的灰度看起來比較統一，你可以通過簡單地調節 Photoshop 圖像->調整->黑白菜單中的控制條來實現。
2. 將上一步得到的灰度圖片轉換為二值圖片，可以通過在 PS 圖像->調整->閾值菜單中設定適當的閾值來實現
3. 確保正確設置了閾值。使用魔棒工具(參數設置：容差 0、取樣點、連續以及消除鋸齒)選擇空白區域，檢查所選區域的邊緣不是因為錯誤的閾值設置而產生的假邊緣。事實上，這個迷宮中從 start 到 end 應該由聯通的空白區域。
4. 人為地在迷宮外部加上邊界，確保迷宮漫游者^_^不會從 start 繞著迷宮跑到終點。:)
5. 選擇語言實現廣度優先搜索算法(BFS)，從 start 處開始讓程序運行。下面的代碼我選擇用 Matlab 實現。正如 Thomas 提到的，沒必要糾結于圖像的表示形式，你可以直接在二值圖像上運行。
以下是用 MATLAB 實現的 BFS 代碼：
這是個簡單的實現，應該很容易就能夠改寫為 Python 或其他語言，下面是程序的運行結果：
提問者更新：
我用 Python 實現了一下 Mikhail 的方法，其中用到了 numpy 庫，感謝 Thomas 推薦。我感覺這個算法是正確的，但是效果不太如預期，以下是相關代碼，使用了 PyPNG 庫處理圖片。
譯注：很遺憾，我用提問者提供的代碼并沒有跑通程序，并且似乎代碼縮進有點問題，而下面其他參與者的代碼能夠執行通過，并且效果很好。
回答 by Joseph Kern：
動態執行效果：
回答 by Jim
使用樹搜索太繁雜了，迷宮本身就跟解路徑是可分的。正因如此，你可以使用連通區域查找算法來標記迷宮中的連通區域，這將迭代搜索兩次這些像素點。如果你想要更好地解決方法，你可以對結構單元使用二元運算(binary operations)來填充每個連通區域中的死路。
下面是相關的 MATLAB 代碼及運行結果：
回答 by Stefano
stefano 童鞋給出了生成搜索過程 GIF 及 AVI 文件的代碼 maze-solver-python (GitHub)
譯文鏈接： http://blog.jobbole.com/62895/