Ricerca del numero di percorsi in una tabella

Question

Tere è una tabella di dimensioni R × C; R righe e colonne C. Un sub-rettangolo della tabella è bloccato. Siamo in grado di spostarci solo verso destra o verso il basso. Qual è il numero di percorsi dalla cella in alto a sinistra alla cella in basso a destra mentre non si passa il sub-rettangolo bloccato?

mio approccio: calcolare il percorso da per righe r2 C = {0 a C1-1} e percorsi da riga r1 C = {c2 + 1, C}

r1, c1, r2, e c2 , la cella in alto a sinistra e la cella in basso a destra del rettangolo bloccato.

Cal Calculate C(n,k) 

My Code:

int R = in.nextInt()-1; 
int C = in.nextInt()-1; 
int r1 = in.nextInt()-1; 
int c1= in.nextInt()-1; 
int r2 = in.nextInt()-1; 
int c2 = in.nextInt()-1; 
long ans=0; 
long temp=0; 
temp+= Cal(R-r2+C-c1,C-c1); 
for(int i=0;i<c1 && r2!=R;i++){ 
    ans+=Cal(i+r2,r2)*(Cal(R-r2+C-i,C-i)-temp); 
} 
temp=0; 

temp+=Cal(r1+c2,r1); 

for(int i=c2+1;i<=C;i++){ 
ans+= (Cal(i+r1,r1)-temp)*Cal(C-i+R-r1,C-i); 

} 
System.out.println(ans); 

Non ricevo la risposta corretta per il mio algoritmo di cui sopra. Per favore aiutami se sto facendo qualcosa di sbagliato.

Sample input: 
8 12 
5 5 8 8 ANS:7008 

Answer 1

faccio fatica a capire la descrizione del vostro algoritmo, quindi non sono sicuro di come aiutare in questo. Tuttavia, penso che un modo per trovare il numero di percorsi potrebbe essere quello di sottrarre quei percorsi che includono le celle nel sub-rettangolo dal totale dei percorsi possibili.

Il numero di percorsi che include una cella specifica è uguale al numero di percorsi dall'angolo superiore sinistro a quella cella, moltiplicato per il numero di percorsi da quella cella all'angolo inferiore destro. E poiché puoi solo spostarti verso il basso o verso destra, tenere conto della colonna sinistra e della riga superiore del sub-rettangolo è sufficiente per tener conto di tutto ciò.

Se hai iniziato in alto a sinistra del sub-rettangolare, si potrebbe procedere come nel seguente esempio (ABCDEF costituiscono il sub-rettangolo):

start X  X  X  X 
    X  A  B  C  X 
    X  D  E  F  X 
    X  X  X  X end 

The sum of paths that include A,B,C,D,E or F equals: 
    Paths to A * Paths from A to end = 2 choose 1 * 5 choose 2     = 20 
+ (Paths to cell above B) * Paths from B to end = 1 * 4 choose 2    = 6 
+ (Paths to cell above C) * Paths from C to end = 1 * 3 choose 1    = 3 
+ (Paths to cell left of D) * Paths from D to end = 1 * 4 choose 1    = 4 

Solution equals: total paths - the number of paths that include A,B,C,D,E or F 
= 7 choose 3 - (20 + 6 + 3 + 4)             = 2 

codice JavaScript:

function f(Rows,Cols,r1,c1,r2,c2){ 
    var r = Rows - r1, 
     total = C(Rows + Cols - 2,Rows - 1), 
     s = C(r1 + c1 - 2,r1 - 1) * C(Cols - c1 + r,r); 

    if (c2 > c1 && r1 > 1){ 
    for (var i=c1+1; i<=c2; i++){ 
     s += C(i + r1 - 3,i - 1) * C(Cols - i + r,r); 
    } 
    } 

    if (r2 > r1 && c1 > 1){ 
    for (var i=r1+1; i<=r2; i++){ 
     s += C(i + c1 - 3,i - 1) * C(Rows - i + Cols - c1,Rows - i); 
    } 
    } 

    return total - s; 
} 

function C(n,k){if(k==0||n==k)return 1;var p=n;for(var i=2;i<=k;i++)p*=(n+1-i)/i;return p} 

uscita:

console.log(f(4,5,2,2,3,4)); 
2 

console.log(f(5,6,2,2,3,3)); 
21 

console.log(f(8,12,5,5,8,8)); 
7008 

Answer 2

suggerisco un approccio di programmazione dinamica per risolvere questo problema. Ciascuna cella "sbloccata" nella scheda avrà un numero associato, il numero di modi per arrivare in basso a destra; attualmente quel numero non è definito in ogni cella.

Potrebbe essere meglio spiegare questo con un esempio. Supponiamo di avere

 
OOOOOO 
OXXOOO 
OXXOOO 
OOOOOO 
OOOOOO 

come la nostra scheda, dove X rappresenta un ostacolo e O è una piazza in cui non abbiamo ancora riempito il numero di percorsi in basso a destra. Ora lavoriamo dall'angolo in basso a destra all'indietro. Inizieremo compilando il numero 1 in basso a destra, anche se ciò potrebbe non avere senso.

Ora i due riquadri più vicini in basso a destra possono essere riempiti. Sono facili.

 
OOOOOO 
OXXOOO 
OXXOOO 
OOOOO1 
OOOO11 

Ora possiamo riempire altre 3 piazze:

 
OOOOOO 
OXXOOO 
OXXOO1 
OOOO21 
OOO111 

In ogni caso quello che stiamo facendo è solo sommando il numero a destra di un quadrato e il numero di sotto di una piazza, dove immaginiamo che gli zeri si stiano dalla parte destra e inferiore del tabellone. Prossimo passo:

 
OOOOOO 
OXXOO1 
OXXO31 
OOO321 
OO1111 

Finora, stiamo ottenendo i coefficienti binomiali, che è quello che ci si aspetterebbe in un problema come questo. Passaggio successivo:

 
OOOOO1 
OXXO41 
OXX631 
OO4321 
O11111 

Altri coefficienti binomiali. Prossimo passo:

 
OOOO51 
OXXA41 
OXX631 
O54321 
111111 

sto usando la lettera A per 10. E 'come se i coefficienti binomiali, ma ci manca un paio di fuori del bordo. Presto questo cambierà comunque. Passaggio successivo:

 
OOOF51 
OXXA41 
OXX631 
654321 
111111 

Nota l'uso di F per 15. Ora le cose si fanno interessanti. Poiché non possiamo attraversare l'ostacolo, associamo 0 alle celle dell'ostacolo. Per riempire il vuoto in alto a destra, aggiungiamo F + 0 = F. Allo stesso modo, 0 + 6 = 6.

 
OOFF51 
OXXA41 
6XX631 
654321 
111111 

Prossimo passo:

 
OFFF51 
6XXA41 
6XX631 
654321 
111111 

Ultimo passo:

 
UFFF51 
6XXA41 
6XX631 
654321 
111111 

Qui sto usando U per 21 = F + 6. Questa è la risposta alla domanda.

La procedura funziona in generale. Possiamo riempire qualsiasi cella per cui conosciamo i numeri a destra e in basso, e gradualmente riempiamo l'intero rettangolo.