迷宮問題
任務：可以輸入一個任意大小的迷宮數據，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；
要求：
在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法；
[問題描述]
走迷宮是實驗心理學中一個古典問題。用計算機解迷宮路徑的程序，就是仿照人走迷宮而設計的，也是對盲人走路的一個機械模仿。
[實現提示]
假設迷宮是一個矩形，我們把它分成許多小方格，在每個小方格上或者已筑成墻或者沒有，這就成為一個迷宮。走迷宮就是從一個小方格沿前后左右四個方向到鄰近的方格，當然不能穿墻。設迷宮的入口是在西北角那個方格，而出口是東南角那個方格。在計算機中，迷宮可用一個矩陣表示。若某小方格是墻，則相應數組變量標為 0，否則為字符1,表示可走的路。現在要編寫一個程序，尋找一條從入口到出口的路線。我們可提出如下一般性問題尋找：一條從任何給定的方格到出口的路線。基本思想是： 在當前位置上向四個（或八個）方位探測前進方位，向探測到的通路方位前進一步，如此循環(huán)，直到迷宮的“出口”，或判斷后宣布這是一個不存在通路的死迷宮。
標簽：
迷宮
輸入
數據
上傳時間：
2013-12-31
上傳用戶：wfl_yy
