Flying Traveler Airline Company

Question

Ich habe ein kleines Problem mit dem Algorithmus dieses Problems.

Problem Statement:

The Flying Reisenden Airline Company (FTAir) will ein Programm Kundenanfragen zu verarbeiten, die von einem gewissen Herkunft Stadt zu einem gewissen Zielstadt zu fliegen. Geben Sie für jeden Kunden an, ob eine Sequenz von FTAir-Flügen von der Ursprungsstadt zur Zielstadt existiert und die Reiseroute - Abfolge der Flüge - erstellt. Eingabe: Drei Eingabetextdateien, die alle Fluginformationen wie folgt angeben: • Die Namen der Städte, die FTAir bedient (mindestens 15 Städte). • Paare von Städtenamen; Jedes Paar repräsentiert den Ursprung und das Ziel eines der Flüge von FTAir. • Paar Städtenamen; Jedes Paar stellt eine Anforderung dar, von einer Ursprungsstadt zu einem Zielort zu fliegen (mindestens 5 Anfragen mit unterschiedlichen Szenarien). Jede Anfrage gilt als One-Way-Flug.

Regeln:

einen Weg vom Ursprung Stadt zum Zielort Stadt finden, wenn exists.Maintain Informationen über die Reihenfolge, in der sie die cities.Do nicht besuchen besucht eine Stadt mehr als once.If gibt es mehrere Wege, Sie können sie alle auflisten und am wenigsten besuchte Städte finden. (wahlweise). Auch über Stack (mit verknüpfter Liste) und Rekursion!

Mein Ansatz ist:

allererst wir eine Datenstruktur müssen alle Eingabetextdateien. Nehmen wir an, wir haben den Namen der Städte in einem Array, ein Paar Städte (Ursprung -> Ziel) in einem 2D-Array und das wiederum in einem 2D-Array.

Für einen Pfad in der Anfrage-Matrix zu Exits, muss es von unserem FTAir bedient werden, so dass wir für jede Anfrage den Ursprung und das Ziel in der Reihe von Städten suchen müssen und wenn beide übereinstimmen, dann nur weiter zu unserem nächsten Schritt.

Nachdem wir eine Übereinstimmung gefunden haben, müssen wir den Anfrageursprung den Flugursprüngen zuordnen, dh wir müssen prüfen, ob ein Flug vom Ursprung benötigt wird, wenn nicht, dann gibt es keinen Pfad für den Reiseantrag .

Aber wenn es eine Übereinstimmung gibt, legen wir diesen Ursprung auf einen Stapel und überprüfen sein Ziel und vergleichen es mit dem gewünschten Ziel, wenn das ein Match ist, haben wir einen direkten Flug und wenn das nicht gesagt wird auf den Stapel und suchen Sie nach dem Ziel als Ursprung in der 2D-Anordnung des Fluges. Fahren Sie mit der Prozedur fort, bis es ein Spiel gibt. Was aber, wenn wir zweimal eine Stadt besuchen? Überprüfen Sie die Daten, die Sie in den Stack eingeben, wenn Duplikationsdaten gefunden werden, brechen Sie ab!

Ich bin nicht in der Lage, meine Gedanken in Code zu konvertieren, kann mir hier jemand helfen?

Answer 1

Schauen wir uns dieses Problem an, indem wir ein Beispiel nehmen.

Wir haben die folgende Liste der Städte, in denen die Airlines

1. Cambridge (A) 
2. Harvard (B) 
3. Hampshire (C) 
4. Toronto (D) 
5. Montreal (E) 
6. Quebec (F) 

gehen jetzt haben wir eine Zuordnungspaare Städte, zwischen denen Flug geht an und aus.

1. (A,B) 
2. (C,D) 
3. (D,E) 
4. (B,C) 

So, jetzt, wenn dies unserer Karte sieht nun so wie diese

A -> B -> C -> D -> E 

mit 5 Städten auf einem Papier zeichnen, wenn Sie mich fragen, ob ich von A nach C reisen möchten, gibt es einen Weg Dafür kannst du einfach ein DFS (A) starten und wenn du C erreichst, dann lautet die Antwort ja.

Angenommen, ich frage, gibt es eine Route von A nach F, dann würde die Anwendung von DFS (A) mich falsch und meine Antwort ist nein.

Um zu überprüfen, ob Sie bereits eine Stadt besucht haben oder nicht, behalten Sie einfach ein glowar-Array als besucht [] und während Sie entlang der DFS-Methode gehen, markieren Sie die Städte als besucht.

Hoffe, dass dies Ihre Zweifel löscht. Stellen Sie weitere Fragen im folgenden Kommentarbereich.