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” .}

Ślimaki , 53 49 bajtów

A^
\.+d!{.l\.+a3(.|~c!~}\.+r!(.u\.+e(.|~},\.,=~d~

Tym razem nie musiałem używać tprzerażającej instrukcji teleportacji. W rezultacie przypadki testowe kończą się natychmiast, zamiast odbierać eony.

Nie golfowany:

A^
r\.+
{
    d\.+
    !{ r\.u \.+ a3 (.|~)}
    r\.+
    !{ d\.l \.+ a3 (.|~)}
},
d\.,
!(dr .)

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ół.

Python 2, 170 131 112 bajtów

def f(C,t=1):i="#".join(C).find("#")+1;return([]<C)*(i<1or(i<t
and f([r[i:]for r in C],t-i))+(i>1)*f(C[1:],i-1))

Funkcja, fprzyjmują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 .

+--+....
|..|....  
+--#<==== o
.....#..
.#......
........

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.

                               A
_
........       ...|////      |....
........       ...|////      |....
...#....  -->  ...#////  -->  ....
.#....#.       .#..//#/       ..#.
........       ....////       ....

   |                           |
   v                           v
                  B
........       ___
........       .#....#.
___#....  -->  ........  -->   +
/#////#/       
////////       

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.

CJam, 85 84 82 81 80 79 bajtów

qN/:Q,(Qz,(:R_T]2/e~e!{'#Qs@{\(\@>}%s-},{_}{(a\L{@+_@\-_{2$\f.=0fe=2&},}h;}w;],

Wypró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:

• Niech szerokość i wysokość siatki być Wi H, odpowiednio.
• Generujemy wszystkie możliwe ścieżki jako odrębne kombinacje W-1kopii 0i H-1kopii W-1(gdzie 0reprezentuje krok poziomy i W-1pionowy). Przechodzimy wszystkie te ścieżki, wielokrotnie biorąc pierwszy element siatki, a następnie pomijając stepkomórki w kolejności odczytu (gdzie stepjest 0lub W-1). Odrzucamy wszystkie ścieżki zawierające #.
• Następnie wielokrotnie usuwamy jedną grupę podobnych ścieżek (które będą wszystkimi ścieżkami podobnymi do pierwszej z pozostałych ścieżek). Sprawdzanie podobnych ścieżek staje się nieco łatwiejsze poprzez złagodzenie ich warunków: zamiast sprawdzania, czy ktoś xsię 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.
• Na koniec zliczamy znalezione grupy, które pozostawiliśmy na dole stosu.