Dfs mit verketteten Liste in 2D-Matrix - C

Question

Ich habe für meine Schule eine Aufgabe, die ich nicht wissen, wie zu lösen, und ich bin fest. Ich habe über dieses Labyrinth laufen:

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

Und in dieser Matrix, muss ich dessen ist, was wichtiger Punkt finden Nachbar verlinkte Liste.

Dies sollte die Ausgabe des Codes sein:

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; 
    } 

ich so etwas tun. Kann mir jemand helfen, wie ich das machen soll? Vielen Dank !

Answer 1

Dies ist ein super herausforderndes Problem für ein Schulprojekt! Aber sieht nach Spaß aus!

Wenn ich das lösen müsste, würde ich;

1. Holen Sie sich alle Adressen jedes Alpha-Zeichen, damit ich weiß, wo alle Startpunkte sind (einfach die Matrix gehen, dass (Schleife in einer Schleife zu tun)
2. konstruieren eine rekursive Funktion (eine Funktion, die Aufruf hält selbst) und ich würde die Funktion dann erlauben,.
   • Laich aus in 4-Vektoren (oben, unten, links, rechts)
   • , wenn die Funktion ein „#“ (Wand) begegnet wäre es zurückgeben nichts und stop,
   • Wenn es einen "." Korridor gefunden hat, war es ld weiter in 4 weiteren Vektoren,
   • , wenn es ein Alpha-Zeichen vorfand, geben Sie dieses Zeichen zurück.
3. für jede bekannte Alpha-Position rufen Sie die rekursive Funktion auf und lassen Sie sie "roamen".
4. für Extrapunkte könnten Sie die parallele Programmierung verwenden, um gleichzeitig jede bekannte Position zu starten :)

gotchas: - achten Sie auf endlose Anrufe - sie wandern nicht über die Grenzen der Matrix