W chińskich warcabach element może się przesuwać, przeskakując nad dowolnym innym elementem lub wykonując sekwencję takich przeskoków. Twoim zadaniem jest znalezienie jak najdłuższej sekwencji skoków.
Wejście
Sekwencja 121 zer lub jedynek, każde reprezentujące miejsce na planszy. Zero oznacza, że miejsce jest puste; jeden oznacza, że miejsce jest zajęte. Pozycje są wymienione od lewej do prawej; od góry do dołu. Na przykład wejście tego ustawienia byłoby
1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111
Wyjaśnienie:
Najwyższe miejsce zajmuje zielony kawałek, więc pierwszą cyfrą na wejściu jest
1
. Drugi rząd ma jedną pustą pozycję, a następnie jedną zajmowaną pozycję, więc01
jest następny. Trzeci rząd jest zajęty, więc111
. Czwarty rząd ma dwa puste i dwa zajęte miejsca (od lewej do prawej), więc0011
. Potem przychodzi pięć0
„S, A1
, i siedem0
” s do następnego wiersza, i tak dalej.
Podobnie jak w tej konfiguracji, róg jest skierowany prosto w górę. Na planszy może znajdować się dowolna liczba elementów (od 1 do 121). Pamiętaj, że elementy o różnych kolorach nie są reprezentowane w różny sposób.
Wynik
Maksymalna długość legalnego skoku przy użyciu dowolnego elementu na planszy. Nie możesz odwiedzić tego samego miejsca więcej niż raz (w tym pozycji początkowej i końcowej). Możesz jednak przeskoczyć nad tym samym kawałkiem więcej niż raz. Jeśli nie ma legalnego przeskoku, wyjście 0
. Nie rozważaj, czy istnieje legalny ruch inny niż chmiel.
Na przykład dane wyjściowe do konfiguracji opisanej powyżej to 3
.
Dane wejściowe i wyjściowe można realizować za pomocą stdin i stdout, argumentów wiersza poleceń, wywołań funkcji lub dowolnej podobnej metody.
Przypadki testowe
Wejście:
0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001
Wyjście: 0
(nie ma dwóch kawałków obok siebie)
Wejście:
0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000
Wyjście: 1
(początkowa konfiguracja dla jednego gracza w lewym górnym rogu)
źródło
Odpowiedzi:
Perl,
345322Edycja: lekko golfa.
Przydałoby się więcej przypadków testowych, ale na razie wygląda na to, że działa. W razie potrzeby dodam komentarze. Z nowymi liniami i wcięciem dla czytelności:
źródło
C
262260Kod w golfa ( usunięto kod debugowania i niepotrzebne białe znaki. Zmieniono z wprowadzania przez stdin na wprowadzanie za pomocą wiersza poleceń i wykorzystano okazję do zadeklarowania tam zmiennej i. Ostatnia edycja: kod przeniesiono do nawiasów
for
pętli, aby zapisać dwa średniki).Wyjaśnienie
Opiera się to na płycie 20x21, która wygląda tak, początkowo wypełniona zerami podczas uruchamiania programu (ta grafika ASCII została wygenerowana przez zmodyfikowaną wersję programu, a gdy
i
pętla liczy się w dół, zero znajduje się w prawym dolnym rogu):Pętla
i
przebiega przez tę tablicę dwukrotnie, używając xiy, aby obliczyć, czy kwadrat rzeczywiście należy do szachownicy, czy nie (wymaga to 6 oddzielnych nierówności w xiy).Jeśli tak, za pierwszym razem runda wypełnia kwadraty, stawiając
0
(fałsz) dla1
(zajętego) i1
(prawda) dla0
(niezajętego). Ta inwersja jest ważna, ponieważ wszystkie kwadraty poza zakresem zawierają już 0, co oznacza, że przypominają zajmowane kwadraty i jasne jest, że nie można do nich wskoczyć, bez potrzeby specjalnego sprawdzania.Za drugim razem, jeśli kwadrat jest zajęty (zawiera 0), wywołuje funkcję,
f
która szuka ruchów.f
wyszukuje rekurencyjnie w 6 możliwych kierunkach zakodowanych przez +/- 1 (poziomo), +/- 20 (pionowo) i +/- 19 (przekątna) zakodowanych w wyrażeniu"AST?-,"[k]-64
. Kiedy znajdzie trafienie, ustawia tę komórkę na 0 (zajęte) przed wywołaniem się rekurencyjnie, a następnie ustawia ją z powrotem na 1 (pustą) po zwróceniu funkcji. Wartość komórki musi zostać zmieniona przed wywołaniem rekurencyjnym, aby zapobiec wskakiwaniu do tej komórki więcej niż raz.Nieskluczony kod
źródło