Problema
Parti dall'angolo in alto a sinistra di una griglia con celle disposte in rows righe e columns colonne. Muoviti solo lungo i bordi delle celle, un bordo alla volta verso destra oppure verso il basso, fino a raggiungere l'angolo in basso a destra. Conta tutte le sequenze di mosse distinte. La griglia non contiene ostacoli.
Una griglia con 2 righe e 3 colonne di celle richiede esattamente 2 mosse verso il basso e 3 verso destra.
Implementa lattice_paths(rows, columns).
Input
rows: Il numero di righe di celle, non di vertici.
columns: Il numero di colonne di celle, non di vertici.
Output
Restituisci il numero di percorsi dall'angolo all'angolo.
Vincoli
0 ≤ rows, columns ≤ 30 e rows + columns ≤ 60. Zero in una dimensione dà un percorso rettilineo. Una griglia 0 × 0 ha un unico percorso vuoto. I conteggi rientrano in un intero con segno a 64 bit.
Esempi
Input:
rows = 2
columns = 3
Output atteso:
expected = 10Input:
long long rows = 2;
long long columns = 3;
Output atteso:
long long expected = 10;Input:
long rows = 2;
long columns = 3;
Output atteso:
long expected = 10;Spiegazione
Ogni percorso contiene cinque mosse. Scegliere quali due siano verso il basso dà dieci percorsi distinti.
Input:
rows = 0
columns = 4
Output atteso:
expected = 1Input:
long long rows = 0;
long long columns = 4;
Output atteso:
long long expected = 1;Input:
long rows = 0;
long columns = 4;
Output atteso:
long expected = 1;Spiegazione
C'è solo il percorso rettilineo composto da quattro mosse verso destra.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ogni percorso è solo un ordinamento delle mosse down e right richieste.
Suggerimento 2
Conta in quanti modi puoi scegliere le posizioni di un tipo di mossa tra tutte le mosse, invece di esplorare i percorsi uno a uno.
Suggerimento 3
Occhio ai casi degeneri: se una dimensione è zero, c’è esattamente un percorso rettilineo, e una griglia 0×0 ha comunque un unico percorso vuoto.
Complessità attesa
tempo O(min(rows, columns)), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.