Jesteś kierowcą taksówki w San Francisco. Jak to typowe dla kierowców taksówek, poruszasz się po siatce, w której jedynymi prawidłowymi kierunkami, które możesz przesunąć, są lewo, prawo, góra i dół. Jednak San Fransisco jest bardzo pagórkowaty, więc odległość między dwoma sąsiednimi skrzyżowaniami niekoniecznie jest taka sama. Mówiąc dokładniej, odległość między skrzyżowaniem na wysokości a
i sąsiednim skrzyżowaniem na wysokości b
będzie wynosić 1 + |a - b|
. Twoim celem jest znalezienie wszystkich najkrótszych ścieżek od miejsca początkowego w lewym górnym rogu mapy do miejsca docelowego w prawym dolnym rogu.
Wejście
Dwuwymiarowa siatka całkowitych wysokości w dowolnym formacie jest najbardziej dogodna (tablica dwuwymiarowa, tablica jednowymiarowa o szerokości i / lub wysokości itp.).
Wynik
Sekwencja kierunków podróży, aby dotrzeć do prawego dolnego rogu wejścia od lewego górnego rogu w możliwie najkrótszej odległości, biorąc pod uwagę odległość między dwoma sąsiednimi przecięciami wysokości a
i b
jest podana wzorem 1 + |a - b|
. Jeśli istnieje wiele rozwiązań, wypisywane są wszystkie rozwiązania.
Chociaż używam U
, D
, L
, i R
na górę, w dół, w lewo iw prawo w poniższych przykładach programu może stosować dowolne cztery odrębne ciągi do reprezentowania kierunków tak długo, jak jest ona zgodna z nich i na wszystkich wejściach.
Przykłady
Input:
0 3 0 0 0
0 2 0 2 0
0 0 0 3 0
Output:
D D R R U U R R D D
Input:
3
Output:
<empty>
Input:
11 11 11
11 11 11
11 11 11
Output:
R R D D
R D R D
R D D R
D R R D
D R D R
D D R R
Input:
7 8 1 -1 0
4 4 6 -1 7
3 4 4 2 8
2 5 2 -1 2
Output:
D R D R R D R
D R D R D R R
To jest golf golfowy, więc wygrywa odpowiedź z najkrótszą liczbą bajtów.
Odpowiedzi:
JavaScript (ES6),
228212200194 bajtówWejście
Jednowymiarowa tablica
a
i szerokośćw
w składni curry(a)(w)
Wynik
Rozdzielona spacjami lista rozwiązań, takich jak
"DRDRRDR DRDRDRR"
Sformatowane i skomentowane
Przypadki testowe
Pokaż fragment kodu
źródło