Ciao a tutti,
pensavo di risolvere il problema trabucco con una dfs + memo
il numero di percorsi con meno caselle sono M+N -2(vero?) per cui basta andare avanti/destra per ridurre i casi
L’unico problema è che non ho idea di come trovare in O(1) la sicurezza di una casella
avete qualche idea?
Con una bfs il tutto può funzionare? Intendo a livello di tempi
Una bfs ha complessità \mathcal O(|V|+|E|) dove V e E\ sono rispettivamente il numero di nodi e il numero di archi. In questo problema abbiamo che il numero di nodi è N\cdot M e il numero di archi (se consideri solo quelli in avanti e a destra) è 2\cdot N\cdot M quindi la complessità della bfs diventa \mathcal O(N\cdot M) che con le assunzioni del problema rientra nei tempi.
piu che per la bfs intendevo la dfs con memorizzazione, ma dovrei aver trovato un modo per risolvere il tutto in O(MN) anche lì
Esistono \mathcal P_{N+M}^{(N,M)} = \frac{(N+M)!}{N!\cdot M!} percorsi di lunghezza minima in una matrice N \times M che vanno da (0,0) a (N-1,M-1) (bonus: dimostralo). Forse ti stai confondendo con la lunghezza di questi percorsi, che è N+M-1.
Prova a pensare a come potresti calcolarti la sicurezza di tutte le caselle in tempo \mathcal O(NM), in modo da poter utilizzare questa informazione successivamente.
Si intendevo la lunghezza dei percorsi, che dovrebbe essere N+M-2,
Alla fine ho fatto una bfs ed ha funzionato
N+M-1 caselle considerando anche quella di partenza, N+M-2 archi.
L’hai risolto, ottimo così
Dimostrazione:
Dato che dobbiamo fare per forza N spostamenti in giù ed M spostamenti a destra, il numero di percorsi che cerchiamo non è altro che il modo in cui possiamo permutare i movimenti “giù” e “destra”. Per farla semplice, il problema è analogo al numero di anagrammi di una parola formata da N lettere “A” e M lettere “B” (ad esempio, con N = 3 e M= 4, il problema si riduce al numero di anagrammi di AAABBBB)
Detto questo, il numero di percorsi non è altro che l’applicazione della formula per calcolare le permutazioni con ripetizione:
\mathcal P(n) = \frac{n!}{k_1!\cdot k_2! \cdot ... \cdot k_m!}
Dove per ogni k_i intendiamo che un certo oggetto a_i è presente nell’insieme k_i volte e per n intendiamo il numero di oggetti che si vuole permutare.
A questo punto, tornando all’esempio della parola con N lettere “A” e M lettere “B”: il numero di oggetti da permutare è chiaramente N + M, l’oggetto “A” è ripetuto N volte, l’oggetto B è ripetuto M volte.
La nostra formula quindi diventa:
\mathcal P() = \frac{(N+M)!}{N!\cdot M!}
(Non riuscivo proprio a trattenermi, scusate :c )