Regeln:
In diesem Spiel beginnen Sie oben in einem rechteckigen Raster der Größe N x M, das aus Wänden und Freiflächen besteht. Die Eingabe besteht aus N Zeilen mit M Zeichen, wobei a .
einen offenen Raum und a x
eine Wand angibt. Ihr Programm sollte die kleinste Zahl K ausgeben, sodass ein Pfad von der oberen linken Ecke zur unteren rechten Ecke (keine Diagonalen) vorhanden ist, der K Wände kreuzt.
Zum Beispiel angesichts der Eingabe:
..x..
..x..
xxxxx
..x..
..x..
Ihr Programm sollte ausgegeben werden 2
.
Andere Beispiele:
Ausgabe 4
:
xxxxx
x.x.x
x.x.x
x..xx
Ausgabe 0
:
.xxxxxxxx
.x...x...
.x.x.x.x.
.x.x...x.
...xxxxx.
Ausgabe 6
:
xx
xx
xx
xx
xx
Zusätzliche Leckerbissen:
Wenn es Ihnen das Leben erleichtert, können Sie N und M als Befehlszeilenparameter angeben.
Zusätzliches Guthaben, wenn Ihr Programm den Pfad in der einen oder anderen Form ausdrucken kann.
Antworten:
Ruby 1,9
(235)(225)(222)(214)Ich weiß nicht, ob dies kürzer ist als ein auf Dijkstra basierendes Programm, aber ich dachte, ich würde einen anderen Ansatz ausprobieren. Hierbei wird Regex in einer Schleife verwendet, um jeden Raum mit der minimalen Anzahl von Wänden zu markieren, die erforderlich sind, um ihn zu erreichen.
Die Eingabe wird als Datei in der Befehlszeile angegeben, d. H.
Ungolfed:
quelle
Perl 5,10 (164)
Sehr ähnlich wie Migimarus Lösung, nur mit diesem zusätzlichen Perl-Touch. 5.10 wird für
\K
in benötigts///
.quelle
Python
406378360348418 ZeichenVereinfachte Dijkstra, da Bewegungen mit Gewicht auf dem
x
Feld sind. Dies geschieht in "Wellen", einer ersten Schleife, in der.
Felder gefunden werden, die die Vorderseite berühren, und auf das gleiche Gewicht eingestellt werden, als wennx
Felder gefunden werden, die die Vorderseite berühren, und auf das+1
Gewicht eingestellt werden. Wiederholen Sie diesen Vorgang, solange keine nicht besuchten Felder mehr vorhanden sind.Am Ende kennen wir das Gewicht für jedes Feld.
Die Eingabe wird als Datei in der Befehlszeile angegeben:
Update: druckt den Pfad.
quelle
C ++ - Version (
610607606584)Implementiert den Dijkstra-Algorithmus.
Nicht Golf:
quelle