witam, potrzebuję rozwiązania w pythonie lub sam algorytm w pseudokodzie do tego zadania:
Julka całymi dnia gra w GTA. Pewnego dnia zauważyła, że jedna mapa składa się z n ulic prowadzących ze wschodu na zachód oraz n ulic prowadzących z północy na południe.Każda droga „wschód-zachód” przecina wszystkie drogi „północ-południe” i vice versa.W ten sposób drogi tworzą kwadratową siatkę n×n skrzyżowań. Julka zastanawia się na ile sposobów może dojechać swoim Dodge’em z południowo-zachodniego krańca na północno-wschodni kraniec tego miasta poruszając się tylko na północ lub na wschód.Wejście W pierwszej i jedynej linii wejścia znajduje się jedna liczba całkowita n (2¬n¬15)oznaczająca liczbę dróg północ-południe (równą liczbie dróg wschód-zachód). Wyjście Program powinien wypisać jedną liczbę oznaczającą liczbę możliwych dróg z południowo-zachodniego krańca na północno-wschodni kraniec miasta składających się wyłącznie z fragmentów prowadzących na północ lub na wschód.Przykład: Dla danych wejściowych:3 Poprawnym wynikiem jest:6
Próbowałem przez długi czas, ale nic. Dla pomocy poprawną odpowiedzią dla 7 to 924, a dla 15 40116600. Z góry dziękuję za odpowiedź.
A co już próbowałeś?
Zauważ, że dla siatki n x n trzeba wykonać n - 1 ruchów na północ i n - 1 ruchów na wschód. Masz więc zbiór ruchów o wielkości 2n - 2, musisz wykonać je wszystkie, żeby dostać się do celu, a pytanie brzmi: na ile różnych sposobów można uporządkować ten zbiór?
Ogólnie rozwiązanie, pomijając pobieranie inputu itp. to jedna linijka.
nie ma czasem zamknietej formuly dla tego problemu?
sprawdz ten filmik
dziękuję za odpowiedzi, dzięki nim poradziłem sobie
def number_of_ways(n,m):
return computeNumberOfWaysToXY(n-1,m-1,
[[0 for i in range(m)] for j in range(n)])
def computeNumberOfWaysToXY(x,y,number_of_ways):
if x==0 or y==0: return 1
if number_of_ways[x][y]==0:
waysTop=0 if x==0 else computeNumberOfWaysToXY(x-1,y,number_of_ways)
waysLeft=0 if x==0 else computeNumberOfWaysToXY(x,y-1,number_of_ways)
number_of_ways[x][y]=waysTop+waysLeft
return number_of_ways[x][y]
print(number_of_ways(15,15))
Ogolnie szukalam ostatnio sposobu na roziwazanie LeetCode UniquePaths III, czyli trudniejsza wersje tego problemu, gdzie START i END moga byc w dowolnych miejscach na gridzie, robot moze isc w 4 kierunkach, musi odwiedzic wszystkie miasta przed dojsciem do END (sciezka hamiltonska albo eulerowska) a w dodatku do niektorych miast na gridzie nie wolno "wchodzic". ma ktos jakis pomysl?
lambdadziara napisał(a):
def number_of_ways(n,m): return computeNumberOfWaysToXY(n-1,m-1, [[0 for i in range(m)] for j in range(n)]) def computeNumberOfWaysToXY(x,y,number_of_ways): if x==0 or y==0: return 1 if number_of_ways[x][y]==0: waysTop=0 if x==0 else computeNumberOfWaysToXY(x-1,y,number_of_ways) waysLeft=0 if x==0 else computeNumberOfWaysToXY(x,y-1,number_of_ways) number_of_ways[x][y]=waysTop+waysLeft return number_of_ways[x][y] print(number_of_ways(15,15))Ogolnie szukalam ostatnio sposobu na roziwazanie LeetCode UniquePaths III, czyli trudniejsza wersje tego problemu, gdzie START i END moga byc w dowolnych miejscach na gridzie, robot moze isc w 4 kierunkach, musi odwiedzic wszystkie miasta przed dojsciem do END (sciezka hamiltonska albo eulerowska) a w dodatku do niektorych miast na gridzie nie wolno "wchodzic". ma ktos jakis pomysl?
Ja bym zapisał sobie tego grida jako graf nieskierowany a potem bfs/dfs po nim, dawno się nie bawiłem w algorytmy, ale z tego co pamiętam to lepszego (szybszego) sposobu chyba nie ma.