Sie haben den Weg durch den Wald gefunden und planen nun, ihn zu befahren. Kurz bevor Sie Ihre Reise beginnen, verwandelt sich der Boden jedoch in Lava.
Sie schaffen es, den nächsten Baum zu huschen (die Bäume sind unerklärlicherweise nicht verbrannt), aber jetzt stehen Sie vor einem Problem: Wie können Sie aus dem Wald herauskommen, wenn der Boden aus Lava besteht? Die Antwort trifft Sie wie eine gute Idee für eine Programmierherausforderung - Sie können Ihren magischen Greifhaken (früher aus einem Stück Kanu hergestellt) verwenden, um durch die Bäume und Äste zu schwingen!
Sie sind sich jedoch nicht sicher, auf welchen Bäumen und Ästen Sie schwingen müssen, um dorthin zu gelangen. Glücklicherweise haben Sie Ihre Programmierkenntnisse und beschließen, ein Programm auf Ihren Arm zu zeichnen, um Ihnen zu sagen, auf welchen Bäumen Sie schwingen sollen. Ihr Arm hat jedoch nicht viel Oberfläche, daher müssen Sie das Programm so klein wie möglich gestalten.
Wir können eine Gesamtstruktur mit einem nby- mArray darstellen. Die folgenden Zeichen bilden das Array:
T: Ein Baum. Sie können hier landen. Sie können Ihren Greifhaken hierfür nicht verwenden. Sie können dies durchschwingen.P: Funktioniert wieT. Du fängst hier an.Q: Funktioniert wieT. Das ist das Ziel.+: Ein Zweig. Sie können hier nicht landen. Hier können Sie Ihren Greifhaken verwenden. Sie können dies durchschwingen.*: Eine menschenfressende Spinne. Wenn du hier landest, stirbst du. Wenn Sie Ihren Greifhaken verwenden, sterben Sie. Wenn Sie dies durchschwingen, sterben Sie.-: Normaler Boden, mit anderen Worten, Lava. Sie können hier nicht landen. Sie können Ihren Greifhaken hierfür nicht verwenden. Sie können dies durchschwingen. Alle Bereiche außerhalb des angegebenen Arrays sind von diesem Typ.
Hier ist ein Beispiel, wie ein Wald aussehen könnte:
y
----T---+------12
---------------11
----T---+---T--10
---------------9
T-+-T-+-T------8
---------------7
------------+--6
----+----------5
+-------+------4
---------------3
----P---+-*-Q--2
---------------1
T-+-T-+-T------0
012345678911111
x 01234
Ich werde mich auf Koordinaten mit der Notation beziehen (x,y), wie auf den Achsen gezeigt.
Sie beginnen von Pund müssen sich auf den Weg machen Q. Dazu schwingen Sie mit Ästen von Baum Tzu Baum . Sie können Ihren Greifhaken an jedem Ast anbringen, der orthogonal zu Ihnen ist, dh an einem Ast, der sich entweder an derselben x- oder y-Position befindet, an der Sie sich befinden. Wenn Sie sich beispielsweise an der Position im Beispielwald befanden , Sie könnten Ihre Enterhaken an den Positionen anbringen , oder . Sie können dies auch dann anhängen, wenn sich zwischen Ihnen und dem Zweig Bäume oder andere Zweige befinden.T+(4,8)(2,8)(6,8)(4,5)
Sobald Sie Ihren Greifhaken an einem Ast befestigt haben, legen Sie eine Strecke in Richtung des Astes zurück, die dem doppelten Abstand zwischen Ihrer Ausgangsposition und dem Ast entspricht. Mit anderen Worten, Ihre Endposition befindet sich im gleichen Abstand vom Ast wie Ihre Startposition, genau auf der gegenüberliegenden Seite. Eine formellere Definition der Funktionsweise der Bewegung finden Sie weiter unten. Ein Index von vist die Endposition, uist die Anfangsposition und bist die Position des Zweigs.
Beachten Sie, dass Sie nicht dorthin gehen können, wenn sich zwischen Ihrer Anfangsposition und Ihrer Endposition eine Spinne befindet. Zum Beispiel ist im Beispielwald das Schwingen von (4,2)nach (12,2)nicht möglich, weil Sie bei auf die Spinne stoßen würden (10,2).
Das Ziel ist es , diese Schwing durch Zweige Verfahren verwendet wird , von dem Punkt , zu reisen , Pzu dem Punkt , Qin den wenigsten möglich Schaukeln. In der Beispielgesamtstruktur lautet der kürzeste Pfad beispielsweise:
- Von
(4,2)bis(4,8)mit(4,5) - Von
(4,8)bis(0,8)mit(2,8) - Von
(0,8)bis(0,0)mit(0,4) - Von
(0,0)bis(4,0)mit(2,0) - Von
(4,0)bis(4,10)mit(4,5) - Von
(4,10)bis(12,10)mit(8,10) - Von
(12,10)bis(12,2)mit(12,6)
Eingang
Die Eingabe erfolgt von jeder geeigneten Methode (STDIN, Befehlszeilenargumente raw_input()usw.), außer dass sie möglicherweise nicht als Variable vorinitialisiert wird . Eingangs beginnt mit zwei Komma getrennte ganze Zahlen , nund mdie die Größe der Platte, dann einen Raum, und dann in den Wald als eine einzige lange Kette. Die Beispielgesamtstruktur als Eingabe würde beispielsweise folgendermaßen aussehen:
15,13 ----T---+-------------------------T---+---T-----------------T-+-T-+-T---------------------------------+------+----------+-------+-------------------------P---+-*-Q-----------------T-+-T-+-T------
Ausgabe
Geben Sie eine durch Leerzeichen getrennte Liste von durch Kommas getrennten Tupeln aus, die die Koordinaten der Zweige angeben, zu denen Sie schwingen müssen. Für die obige Eingabe wäre die Ausgabe beispielsweise:
4,5 2,8 0,4 2,0 4,5 8,10 12,6
Sie haben vielleicht bemerkt, dass dies nicht der einzige kürzeste Weg durch den Wald ist - tatsächlich dauert es genau die gleiche Anzahl von Schaukeln, wenn Sie von dort aus nach (8,8)unten gehen , nach (8,0)links gehen (4,0)und wie gewohnt weitermachen . In diesen Fällen kann Ihr Programm Mai Ausgabe entweder der kürzesten Wege. Also die Ausgabe:
4,5 6,8 8,4 6,0 4,5 8,10 12,6
ist auch erlaubt. Dies ist Code-Golf , daher gewinnt der Eintrag mit der kürzesten Anzahl von Bytes. Wenn Sie Fragen haben oder meine Erklärung nicht klar ist, fragen Sie in den Kommentaren.
quelle
15,13da das Array 13 x 15 groß ist.Antworten:
GolfScript, 196 Zeichen
Ein schreckliches Stück GolfScript-Code - aber es funktioniert wie gewünscht. Der Algorithmus ist nicht optimal, aber ziemlich schnell. Das Beispiel läuft auf meinem Computer deutlich unter einer Sekunde.
quelle