在2d矩陣中使用鏈接列表的Dfs - C

我得到了我的學校項目的任務，我不知道如何解決，我卡住了。我必須跑過這個迷宮：在2d矩陣中使用鏈接列表的Dfs - C

#T########### 
    #.#...R.....# 
    #.###.#.###.# 
    #...Q.#...#.# 
    #.#####C###F# 
    #.A.........# 
    #B#####E#K#L# 
    #.......#.#.# 
    ###D#H###.#.# 
    #...#...J.P.# 
    #G###X#####.# 
    #.........N.# 
    #############

而在這個矩陣中，我必須找到哪個重要點是其鄰居使用鏈接列表。

這應該是代碼的輸出：

A: L K F E C T Q B 
    B: H E D T Q A 
    C: L K F E A R F 
    D: G H E B 
    E: H D B L K F C A 
    F: L K E C A R C 
    G: X N D 
    H: X J E D B 
    J: X H P K 
    K: P J L F E C A 
    L: P N K F E C A 
    N: X G P L 
    P: N L K J 
    Q: R T B A 
    R: F C Q 
    T: Q B A 
    X: N G J H 


    int rekurzia(int x,int y) 
    { 
    if ((x < 0) || (x > MAX - 1) || (y < 0) || (y > MAX - 1)) 
     return false; 
    if((matica[x][y] >= 'A') && (matica[x][y] <= 'Z')) 
     printf("%c\n", matica[x][y]); 
    if (matica[y][x] != '.') 
     return false; 
    if (rekurzia(x,y-1) == true) 
     return true; 
    if (rekurzia(x+1,y) == true) 
     return true; 
    if (rekurzia(x,y+1) == true) 
     return true; 
    if (rekurzia(x-1,y) == true) 
     return true; 
    return false; 
    }

我做這樣的事情。有人能幫我做我應該怎麼做嗎？謝謝！

來源

2017-05-09 Rastislav

太如現在所述那樣廣泛。發佈你的代碼並描述你的問題。 – LPs

這是一個針對學校項目的極具挑戰性的問題！但看起來很有趣！如果我不得不解決這個問題，我會;

獲取每個字母字符的所有地址，所以我知道，所有的啓動點（走純粹矩陣做一個循環內部（循環）
構建一個遞歸函數（即保持調用一個函數然後自己），我將允許功能;
- 產卵關中4個向量（上，下，左，右）
- 如果函數遇到一個「＃」（牆），它會返回任何結果和停止，
- 如果它找到了一個「。」走廊它wou ld在4個以上的向量中繼續，
- 如果遇到字母字符，則返回該字符。
對於每個已知的alpha位置調用遞歸函數並讓它「漫遊」。
加分，你可以使用並行編程，同時開始每個已知位置:)

陷阱： - 注意無盡的通話 - 不漫遊過去矩陣的邊界

來源

2017-05-09 09:33:13

這裏沒有明顯的需要使用遞歸。它應該像往常一樣，避免像瘟疫一樣，只能用作最後的手段。 – Lundin

我想知道如何用線性程序來解決這個問題。我設法用c＃編寫了一個遞歸函數，它非常緊湊。我的結果在技術上更爲正確，因爲我首先找到最接近的點，而上面的結果並非如此。 –

所有的遞歸都是保存以前的位置。它總是可以用一個循環和一個LIFO來代替之前的位置。或者，也可以使用包含指向父節點的指針的BST。唯一一次遞歸是「緊湊」的是編譯器設法展開它，這通常需要尾遞歸。什麼是「緊湊」，你的源代碼，機器代碼或堆棧使用情況？這三個中的第一個是非常不相關的。 – Lundin

在2d矩陣中使用鏈接列表的Dfs - C

回答

相關問題