Tempo minimo per attraversare il fiume

Question

Una rana sta cercando di raggiungere l'altro lato del fiume. Inizialmente sul lato della banca (posizione -1) e vuole raggiungere l'altro lato della banca (posizione N).

La rana può saltare qualsiasi distanza tra 1 e D. Se D è minore di N, la rana non può saltare direttamente. Ci sono pietre per aiutare la rana a saltare, ma saranno fuori dall'acqua solo dopo un certo periodo di tempo, dato che l'acqua è in costante diminuzione. La rana può saltare da e verso le pietre solo quando la pietra è fuori dall'acqua. Le pietre nel fiume sono descritte nella matrice A costituita da N interi. A [K] rappresenta un tempo in cui una pietra in posizione K sarà fuori dall'acqua. A [K] = - 1 significa nessuna pietra in quella posizione. Lo scopo è trovare il primo momento in cui la rana possa raggiungere l'altra sponda.

Esempio D = 3, N = 6.
A [0] = 1

A [1] = - 1

A [2] = 0

A [3] = 2

A [4] = 3

a [5] = 5

al tempo 2, 3 pietre saranno fuori dall'acqua e la rana può saltare l'altra banca in 3 salti.

Qualcuno potrebbe aiutarmi con l'approccio? Non riesco a pensare ad un approccio efficiente per risolvere questo.

Answer 1

Ecco un'implementazione piuttosto semplice.

Utilizzare una matrice che è il numero di pietre più 2: -1 = banco della rana e N = altra banca.

Si noti l'uso delle macro di accesso A e J per consentire l'indice negativo:

// frogjmp/frogjmp -- jump frog across river 

#include <stdio.h> 
#include <stdlib.h> 
#include <unistd.h> 
#include <string.h> 
#include <errno.h> 

#define sysfault(_fmt...) \ 
    do { \ 
     printf(_fmt); \ 
     exit(1); \ 
    } while (0) 

FILE *xfin; 

int Dmax;        // maximum allowable jump distance 
int Nmax;        // number of stones 

// list of positions in river: 
// value is number of rounds needed to uncover a stone as valid jump-to place 
// -1 -- no stone at position 
// position is usable as jump-to point iff value is zero 
// 
// special index values: 
//  A(-1) is initial frog position (starting river bank) 
//  A(Nmax) is the destination river bank 
// 
// the layout of this [and J] are: 
// frog's bank position | stones[Nmax] | other bank position 
int *Aptr;        // river state 
#define A(_idx)  Aptr[(_idx) + 1] 

int jmpcnt;        // number of jumps used 
int *Jptr;        // jump history 
#define J(_idx)  Jptr[(_idx) + 1] 

int Tcur;        // current time period/round 
int Tmax;        // maximum time for all stones uncovered 

// getval -- read in numeric value 
int 
getval(const char *sym,int idx) 
{ 
    char prompt[100]; 
    char *bp; 
    char linebuf[1000]; 
    int val; 

    bp = prompt; 
    bp += sprintf(bp,"%s",sym); 
    if (idx >= 0) 
     bp += sprintf(bp,"[%d]",idx); 
    bp += sprintf(bp,": "); 

    // interactive -- show prompt 
    if (xfin == stdin) { 
     fputs(prompt,stdout); 
     fflush(stdout); 
    } 

    // get line 
    bp = fgets(linebuf,sizeof(linebuf),xfin); 
    if (bp == NULL) 
     sysfault("getval: premature EOF\n"); 

    // isolate the number 
    bp = strtok(linebuf," \t\n"); 
    if (bp == NULL) 
     sysfault("getval: empty line\n"); 

    // get the number value 
    val = atoi(bp); 

    // file input -- show prompt and value read 
    if (xfin != stdin) { 
     fputs(prompt,stdout); 
     printf("%d\n",val); 
    } 

    return val; 
} 

// chkbad -- check for impossible (too many -1 values in a row) 
void 
chkbad(int lo) 
{ 
    int hi; 
    int idx; 
    int badflg; 

    badflg = 1; 
    hi = lo + Dmax; 

    if (hi > Nmax) { 
     hi = Nmax; 
     badflg = 0; 
    } 

    for (idx = lo; idx < hi; ++idx) { 
     if (A(idx) >= 0) { 
      badflg = 0; 
      break; 
     } 
    } 

    if (badflg) 
     sysfault("chkbad: impossible\n"); 
} 

// jmpshow -- show river state with jumps 
void 
jmpshow(void) 
{ 
    int idx; 
    int val; 

    printf("A:"); 

    for (idx = 0; idx <= Nmax; ++idx) { 
     val = A(idx); 
     printf(" %d=%d%s",idx,val,J(idx) ? "<" : " "); 
    } 

    printf("\n"); 
} 

// frogjmp -- jump the frog to the farthest reachable position from current one 
// RETURNS: new frog position (-1=nothing valid) 
int 
frogjmp(int frogcur) 
// frogcur -- current frog position 
{ 
    int idx; 
    int lo; 
    int hi; 
    int val; 
    int best; 

    // get range of possible jump-to positions from the current frog position 
    lo = frogcur + 1; 
    hi = frogcur + Dmax; 
    if (hi > Nmax) 
     hi = Nmax; 

    // find the farthest/best jump (i.e. the _last_ valid jump we find here) 
    // A values: 
    // <0 -- no stone in position 
    // 0 -- stone/position can be jumped to now 
    // >0 -- stone can't be jumped to now -- will be uncovered in future round 
    best = -1; 
    for (idx = lo; idx <= hi; ++idx) { 
     val = A(idx); 
     if (val == 0) 
      best = idx; 
    } 

    // found a landing point -- advance jump count and mark it as being jumped 
    // to 
    if (best >= 0) { 
     jmpcnt += 1; 
     J(best) = 1; 
    } 

    return best; 
} 

// dotime -- process current time period 
// RETURNS: 1=frog on other side 
int 
dotime(void) 
{ 
    int frogcur; 
    int idx; 
    int doneflg; 

    printf("dotime: time %d\n",Tcur); 

    // reset the jump history 
    jmpcnt = 0; 
    for (idx = -1; idx <= Nmax; ++idx) 
     J(idx) = 0; 
    J(-1) = 1; 

    // show state at start of time period 
    jmpshow(); 

    // frog always starts here 
    frogcur = -1; 

    doneflg = 0; 
    while (1) { 
     // find the best position (farthest) to jump to from the current 
     // position 
     // bug out if no place to jump to found within this round (i.e. we 
     // can't get to the other side without a new drain operation) 
     frogcur = frogjmp(frogcur); 
     if (frogcur < 0) 
      break; 

     // stop when frog gets to the other side -- we're done 
     if (frogcur >= Nmax) { 
      doneflg = 1; 

      printf("dotime: frog landed at time %d after %d jumps\n", 
       Tcur,jmpcnt); 
      jmpshow(); 

      break; 
     } 

     // show state after current jump 
     jmpshow(); 
    } 

    return doneflg; 
} 

// dodrain -- drain river by one level 
void 
dodrain(void) 
{ 
    int idx; 
    int val; 

    // bump down the level for each stone: the time remaining before it becomes 
    // accessible/usable 
    // we only do this for "covered" stones, never for non-existent ones or 
    // ones that are already "uncovered" 
    for (idx = 0; idx < Nmax; ++idx) { 
     val = A(idx); 
     if (val > 0) 
      A(idx) = val - 1; 
    } 
} 

// dofile -- process test 
void 
dofile(void) 
{ 
    int idx; 

    // get the maximum jump the frog can do 
    Dmax = getval("D",-1); 

    // get the number of stones/positions in the river 
    Nmax = getval("N",-1); 

    // get enough space for the [in river] stone positions + the bank positions 
    Aptr = malloc(sizeof(int) * (Nmax + 2)); 
    Jptr = malloc(sizeof(int) * (Nmax + 2)); 

    // get values for all the stones in the river 
    Tmax = -1; 
    for (idx = 0; idx < Nmax; ++idx) { 
     Tcur = getval("A",idx); 
     A(idx) = Tcur; 
     if (Tcur > Tmax) 
      Tmax = Tcur; 
    } 

    // the river banks are always accessible jump points (i.e. they're _not_ 
    // "covered") 
    A(-1) = 0; 
    A(Nmax) = 0; 

    // show the initial state after reading inpu 
    jmpshow(); 

    // check for impossible river 
    for (idx = 0; idx < Nmax; ++idx) 
     chkbad(idx); 

    // do all possible time periods 
    for (Tcur = 0; Tcur <= Tmax; ++Tcur) { 
     // test the current river state to see if frog can make it across now 
     // stop when we're done 
     if (dotime()) 
      break; 

     // we were blocked by some inaccessible jump 
     // drain the river by a level in prep for next time period 
     // this makes _some_ stones [based on their updated values] as valid 
     // jump-to points for the next round that may not have been accessible 
     // during the current round 
     dodrain(); 
    } 

    free(Aptr); 
    free(Jptr); 
} 

// main -- main program 
int 
main(int argc,char **argv) 
{ 
    char *cp; 

    --argc; 
    ++argv; 

    if (argc <= 0) { 
     xfin = stdin; 
     dofile(); 
    } 

    for (; argc > 0; --argc, ++argv) { 
     cp = *argv; 
     xfin = fopen(cp,"r"); 
     if (xfin == NULL) 
      sysfault("main: unable to open '%s' -- %s\n",cp,strerror(errno)); 
     dofile(); 
     fclose(xfin); 
    } 
} 

---

Ecco l'output del programma per il vostro ingresso ad esempio:

D: 3 
N: 6 
A[0]: 1 
A[1]: -1 
A[2]: 0 
A[3]: 2 
A[4]: 3 
A[5]: 5 
A: 0=1 1=-1 2=0 3=2 4=3 5=5 6=0 
dotime: time 0 
A: 0=1 1=-1 2=0 3=2 4=3 5=5 6=0 
A: 0=1 1=-1 2=0< 3=2 4=3 5=5 6=0 
dotime: time 1 
A: 0=0 1=-1 2=0 3=1 4=2 5=4 6=0 
A: 0=0 1=-1 2=0< 3=1 4=2 5=4 6=0 
dotime: time 2 
A: 0=0 1=-1 2=0 3=0 4=1 5=3 6=0 
A: 0=0 1=-1 2=0< 3=0 4=1 5=3 6=0 
A: 0=0 1=-1 2=0< 3=0< 4=1 5=3 6=0 
dotime: frog landed at time 2 after 3 jumps 
A: 0=0 1=-1 2=0< 3=0< 4=1 5=3 6=0< 

---

Aggiornamento:

Il programma itera attraverso periodi di tempo che vanno dallo stato iniziale all'ultimo round (es. il più alto valore "di pietra"): T0, T1, ...

Ad ogni giro, la rana parte dalla riva del fiume iniziale. Per una data posizione della rana, viene calcolata la posizione "jump-to" più lontana, basata sul massimo intervallo di salto possibile della rana e sullo stato corrente delle pietre all'interno di tale intervallo. Se viene trovata una tale posizione di salto valida (ovvero la posizione di salto in posizione ha un valore zero), il processo si ripete finché la rana non si trova sull'altro banco.

Se non è possibile trovare la posizione di salto (vale a dire il progresso è bloccato da pietre inesistenti e/o coperte), i livelli di "copertura" di pietra sono decrementati di uno. Quindi, viene avviato un nuovo round.

Answer 2

Ecco una possibile soluzione:

Iterare matrice facendo avanzare l'indice (i) per la pietra (A[i]) con il minor tempo nell'intervallo A[i+1..i+D]. In ogni passaggio, mantenere il tempo massimo trovato finora (maxTime = max(maxTime, A[i]). Ripeti questo processo fino a i < N-D. Al termine del processo, viene trovato il tempo massimo in maxTime.

La complessità è O ((N-D) D).