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.
2 Mi Piace
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.
2 Mi Piace
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ì
2 Mi Piace
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 )
6 Mi Piace