Finden einer "Spur" in 2-D-Dimension-Arrays

Question

Ich weiß nicht, wie man diese Frage herausfinden, ich bin nur ein Anfänger in der Informatik.

Die Eingabe besteht aus 2D-Array-A [n] [n] -Zahlen, die die topographische Karte der geografischen Oberfläche darstellen. Zu den Eingaben gehört auch ein Startort (r, c). Bezug auf Eintrag A [r] [c]

Wenn Sie Wanderwege planen, sind Sie an die Höhenunterschiede zwischen benachbarten Einträgen gebunden. Eine Person könnte zwischen zwei benachbarten Orten durchqueren, wenn ihre Höhen sich um nicht mehr als 2) unterscheiden. Die Anpassung folgt nur den 4 Standard-Himmelsrichtungen (ich nehme also keine Diagonalen an). Daher wird ein Punkt auf der Karte als erreichbar erachtet, wenn er von A [r] [c] durch eine beliebige Folge benachbarter Ganzfelder überquert werden kann.

Schreiben Sie einen Algorithmus, der alle erreichbaren Positionen berechnet. Die Ausgabe wird eine andere 2D-Anordnung R [n] [n] mit Wahr/Falsch-Werten sein. (Ich nehme wahr wahr bedeutet, erreichbar, falsch bedeutet unerreichbar)

Wenn ich diese Frage richtig verstehe, kann ich folgende Matrix erstellen. (Nehme A [10] [10] wie folgt aus A sieht [0] [0] :)

50 51 54 58 60 60 60 63 68 71 
48 52 51 59 60 60 63 63 69 70 
44 48 52 55 58 61 64 64 66 69 
44 46 53 52 57 60 60 61 65 68 
42 45 50 54 59 61 63 63 66 70 
38 42 46 56 56 63 64 61 64 62 
36 40 44 50 58 60 66 65 62 61 
36 39 42 49 56 62 67 66 65 60 
30 36 40 47 50 64 64 63 62 60 
50 50 50 50 50 50 50 50 50 50 

Sowohl Süden und Osten verfahrbar sind von A [0] [0] so erreichbar Einträge würde:

50 51 54 58 60 60 60 63 68 71 
48 52 51 59 60 60 63 63 69 70 
44 48 52 55 58 61 64 64 66 69 
44 46 53 52 57 60 60 61 65 68 
42 45 50 54 59 61 63 63 66 70 
38 42 46 56 56 63 64 61 64 62 
36 40 44 50 58 60 66 65 62 61 
36 39 42 49 56 62 67 66 65 60 
30 36 40 47 50 64 64 63 62 60 
50 50 50 50 50 50 50 50 50 50 

so kann ich feststellen, dass meine resultierende Array

1 1 0 0 0 0 0 1 0 0 
1 1 1 0 0 0 1 1 0 0 
0 0 1 0 0 0 1 1 1 0 
0 0 1 1 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 1 0 
0 0 0 1 1 0 0 0 1 1 
0 0 0 0 1 1 0 0 1 1 
0 0 0 0 1 1 0 0 0 1 
0 0 0 0 0 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 

Unser Professor bitten, uns dies in Pseudo-Code zu implementieren sein sollte. Ich weiß nicht, wie man Vergleiche für zwei Nachbarpunkte und 4 Richtungen des Punktes macht. Jeder kann mir ein paar Ideen geben?

Answer 1

Es ist nur Flut füllen. Sie benötigen eine Warteschlange und einen indexadressierbaren Vektor von "besuchten" Flags. Setzen Sie die Wurzel in die Warteschlange. Wenn die Warteschlange nicht leer ist, nimm das erste Element und suche nach erreichbaren Orten N, S, E, W. Dann überprüfe, ob sie besucht wurden. Wenn nicht, markiere sie als besucht und setze sie in die Warteschlange.