tło
Zbudowałem prosty tor przeszkód, umieszczając pudła w prostokątnym pokoju. Teraz chcę policzyć liczbę zasadniczo różnych sposobów rozwiązania tego problemu. Chcę, żebyś napisał mi program do tego.
Wkład
Twoje dane wejściowe to niepusty prostokątny układ znaków .#
. Kropki .
to pusta przestrzeń i #
są przeszkodami.
Ścieżka przez przeszkody Kurs rozpoczyna się w lewym górnym rogu, a kończy się w prawym dolnym rogu i idzie tylko w prawo lub w dół. Prawidłowa ścieżka nie może również przechodzić przez przeszkodę. Oto kilka przykładów narysowanych przy pomocy +
-znaków:
Valid path Invalid path Invalid path Invalid path
++........ ++........ +++++..... ..+.......
.++++++#.. .+.....#.. ....+++#++ ..++...#..
......+#.. .+.++++#.. .......#.+ ...+++.#..
....#.++++ .+++#.++++ ....#....+ ....#+....
Dwie ścieżki są zasadniczo podobne 1, jeśli jedną można przekształcić w drugą, przesuwając jedną +
po drugiej . Ścieżki pośrednie również muszą być prawidłowe, abyś nie mógł zgiąć ścieżki nad przeszkodą. Na przykład pierwsze dwie ścieżki tutaj są zasadniczo podobne, ale trzecia zasadniczo różni się od nich, ponieważ nie można pokonywać dwóch przeszkód:
++........ +......... +++++++++.
.+++++.#.. ++.....#.. .......#+.
.....+.#.. .++++++#.. .......#++
....#+++++ ....#.++++ ....#....+
Wydajność
Twój wynik to liczba zasadniczo różnych ścieżek przez tor przeszkód. Innymi słowy, jeśli wszystkie prawidłowe ścieżki są podzielone na klasy zasadniczo podobnych ścieżek, wynikiem jest liczba klas. Zauważ, że liczba ta może wynosić 0, jeśli nie ma prawidłowych ścieżek.
Zasady i punktacja
Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Nie ma żadnych ograniczeń czasowych, z wyjątkiem tego, że powinieneś ocenić swój program na każdym przypadku testowym przed jego przesłaniem.
Przypadki testowe
....
....
.... => 1
...#
....
...# => 0
#..#
..#.
.... => 0
......
......
..##..
......
...... => 2
......
...#..
......
..#...
#..... => 3
......
..#...
......
....#.
#..... => 4
.......
##.....
....###
...#...
..##.#.
#....#.
..#.... => 0
......#.
..##....
...#....
.......#
....#...
.##...#.
....#...
##...... => 7
.........
.#.#.#.#.
.........
#.#...#.#
.........
.#.#.#.#.
......... => 17
..........
.#........
..........
.....#....
#.........
........#.
......#...
.......... => 10
.........
.#.......
.........
...#.....
.........
.....#...
.........
.......#.
......... => 16
1 Prawidłowy termin techniczny to „homotopiczny” .
źródło
+
na raz ”? Czy to oznacza, że zasadniczo podobne ścieżki muszą mieć tę samą długość?+
” rozumiem w istocie, że jeden róg ścieżki jest odwrócony w róg przeciwnego kierunku.Odpowiedzi:
Ślimaki ,
5349 bajtówTym razem nie musiałem używać
t
przerażającej instrukcji teleportacji. W rezultacie przypadki testowe kończą się natychmiast, zamiast odbierać eony.Nie golfowany:
Opcje
A^
oznaczają rozpoczęcie w lewym górnym rogu i policzenie wszystkich pasujących ścieżek. Główną ideą jest sprawdzenie warunków kanoniczności ścieżek. Szczerze mówiąc, nie spodziewałem się, że zadziała, ale przybijał przypadki testowe, więc ... Próbuje to sprawdzić, czy w ramach bieżącej ścieżki wybrano najbardziej zachłanną trasę, czyli idąc w prawo tyle razy, ile to możliwe , w dół tyle razy, ile to możliwe itp. bez przekraczania przeszkód. Odbywa się to poprzez sprawdzenie, po 1 lub więcej razy przesunięciu w prawo, a następnie 1 lub więcej razy w dół, że nie można było dotrzeć do następnego kwadratu (który musi być po prawej), przechodząc jeszcze raz w prawo w poprzednim prawym segmencie. Analogiczny warunek jest również sprawdzany po przejściu w prawo, a następnie w dół.źródło
Python 2,
170131112 bajtówFunkcja,
f
przyjmująca tor przeszkód jako listę rzędów i zwracająca liczbę zasadniczo różnych ścieżek.Wyjaśnienie
Podstawowa koncepcja jest następująca: wybieramy określoną przeszkodę, o , tak aby w polu ograniczającym o i lewym górnym rogu nie było żadnych innych przeszkód .
Następnie rozważamy dwa pod-kursy na wschodzie i na południe od o . Rozważamy tylko jeden z tych podbiegów, jeśli o można faktycznie przejść z kierunku, który do nich prowadzi, to znaczy z północy, aby dostać się na wschód, i z zachodu, aby dostać się na południe. Rozwiązujemy problem dla każdego z wybranych pod-kursów i zwracamy sumę wyników. Te liczby odpowiadają liczbie zasadniczo różnych ścieżek przy przekraczaniu O z lewej i z prawej strony, odpowiednio, w związku z dwóch uzyskiwanych zestawów ścieżek są zasadniczo różne. Ponieważ nie ma przeszkód między punktem początkowym a o, istnieje ścieżka między punktem początkowym a dowolnym punktem wejściowym do każdego z tych regionów, a wszystkie takie ścieżki, które prowadzą do tego samego punktu, są zasadniczo podobne, stąd powyższa suma jest pełną liczbą zasadniczo różnych ścieżek w całym przebiegu.
Sprawy nieco komplikuje fakt, że sam tor przeszkód nie przenosi wszystkich potrzebnych informacji. Na przykład rozważ kurs B na powyższym schemacie. Samo w sobie nie możemy ustalić, czy każdą z przeszkód można pokonać z północy. Gdyby B było kursem wejściowym, ponieważ wszystkie ścieżki zaczynają się w lewym górnym rogu, żadna przeszkoda nie mogłaby zostać przekroczona z północy, ale ponieważ możemy dotrzeć do B z każdej strony lewej przeszkody podczas przekraczania o ze wschodu , powinniśmy traktować tę przeszkodę tak, jakby można ją było pokonać z północy podczas rozwiązywania kursu; to samo nie dotyczy jednak właściwej przeszkody, której nie można przekroczyć z tego kierunku.
Przeszukujemy te dodatkowe informacje, określając wraz z torami przeszkód liczbę znaków w pierwszym rzędzie, zaczynając od lewej strony, od której ścieżka może się zaczynać. Na powyższym schemacie jest to przedstawione jako ciągła linia obok każdego kursu. Chociaż technicznie musimy również określić odpowiednią liczbę znaków wzdłuż pierwszej kolumny, od której ścieżka może się zaczynać, tak jak w przypadku pododdziału A , w praktyce zawsze wybieraliśmy najwyższą przeszkodę, więc ta informacja nie jest wymagana .
Rzeczywisty wybór o jest następujący: Udajemy, że po każdym rzędzie oprócz ostatniego znajduje się przeszkoda (tzn. Ma
#
do niej dopisaną) i wybieramy pierwszą przeszkodę na wynikowym kursie, w kolejności czytania. W przypadku rzędów (innych niż ostatni), które początkowo nie miały żadnych przeszkód, oznacza to skutecznie, że je pomijamy (zwracając uwagę, że ścieżka poniżej może zaczynać się od dowolnej postaci w górnym rzędzie). W końcu otrzymujemy kurs, który ma pojedynczy rząd bez przeszkód, dla którego istnieje tylko jedna możliwa ścieżka.źródło
CJam,
858482818079 bajtówWypróbuj online. Lub uruchom cały zestaw testów.
Wydajność tego rozwiązania jest prawdopodobnie dość okropna, ale rozwiązuje każdy przypadek testowy w ciągu kilku sekund.
Wyjaśnienie
Później będę musiał dodać pełny podział kodu, ale idea algorytmu jest następująca:
W
iH
, odpowiednio.W-1
kopii0
iH-1
kopiiW-1
(gdzie0
reprezentuje krok poziomy iW-1
pionowy). Przechodzimy wszystkie te ścieżki, wielokrotnie biorąc pierwszy element siatki, a następnie pomijającstep
komórki w kolejności odczytu (gdziestep
jest0
lubW-1
). Odrzucamy wszystkie ścieżki zawierające#
.x
się poruszył, sprawdzamy, czy ścieżki różnią się dokładnie w dwóch miejscach. W takim przypadku te dwa miejsca zostaną zamienione na ruch pionowy i poziomy. Powoduje to przesunięcie całego segmentu między tymi ruchami po przekątnej o jedną komórkę. Ale jeśli obie te ścieżki są prawidłowe, przesunięcie dowolnej części ścieżki o jedną komórkę po przekątnej nie może przekroczyć przeszkody, więc są one podobne. Wciąż musimy znaleźć przechodnie zamknięcie, więc kontynuujemy to, dopóki nie znajdziemy już podobnych ścieżek przed przejściem do następnej grupy.źródło