用stack走迷宮

mmaammaa

如提
要先讀一個文字檔內容  

wwwwwwwww
A     www       B
w    www    ww
w        ww   ww
w                ww
ww wwwww w
w                   w
www www    w
wwwwwwwww

九成九的地圖  大概像上面那樣
...

瀏覽完整內容，請先 註冊 或 登入會員

要用到graph search的概念，你把每一個位置都想成是一個node，node的資料結構可以自己設計，總之牆壁就是不能走的node，然後空白是可以走的node。
所以就是在parse這份地圖時就要把所有的node初始化(就是用stack設計出你可以用的資料結構)，接下來就看你要用什麼演算法來找到終點。

補充內容 (2012-4-1 03:35 PM):
可以參考看看Greedy algorithm

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

...

瀏覽完整內容，請先 註冊 或 登入會員

因為不想花太多時間寫的很草，就參考用，需要整理！大概是這樣，用DFS的走法，順時鐘選方向有路就走，並把目前節點狀態推入堆疊，建立一個mask陣列判斷已走位置避免重走！

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

...

瀏覽完整內容，請先 註冊 或 登入會員

orsinobbb

可以搜尋DFS(深度優先搜尋)+stack關鍵字
遞迴方式也能解。
吃過虧的題目

qitar888

應該是dfs就可以了
dfs(x,y){
    isUsed[x][y] = 1;
    if (x = ansX, y = ansY) return;
    if(isUsed[x+1][y] = 0)dfs(x+1,y) ;
    if(isUsed[x-1][y] = 0)dfs(x-1,y) ;
    if(isUsed[x][y+1] = 0)dfs(x,y+1) ;
    if(isUsed[x][y-1] = 0)dfs(x,y-1) ;
     return;
}
如果要搭配stack，就是在呼叫函數的地方改成stack.push，然後用while判斷stack不為無就可以了
...

瀏覽完整內容，請先 註冊 或 登入會員