algorithm - 渡河的最短时间

Question

一只青蛙正试图到河的另一边。最初是在银行的一边（位置-1），想去银行的另一边（位置n）。
青蛙可以跳1到d之间的任何距离。如果d小于n，青蛙就不能直接跳。有石头可以帮助青蛙跳跃，但它们只有在一定时间后才会出水，因为水不断减少。青蛙只有在石头离开水的时候才能在石头上跳来跳去。
河流中的石头被描述成由n个整数组成的数组a。
a[k]表示位置k处的石头出水的时间。a[k]=-1表示该位置没有石头。我们的目标是寻找青蛙最早到达对岸的时间。
例d=3，n=6。
A[0]=1
A[1]=-1
A[2]=0
A[3]=2
A[4]=3
A[5]=5
第二次，三块石头将从水里出来，青蛙可以三次跳到另一个河岸。
有人能帮我一下吗？我想不出一个有效的方法来解决这个问题。

Answer 1

这里有一个非常简单的实现。
使用一个数组，它是石头的数量加上2:-1=青蛙的银行，和N=其他银行。
注意使用access宏A和J来允许负索引：

// 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);
    }
}

下面是示例输入的程序输出：

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<

更新：
程序在从初始状态到最后一轮（即最高的“stone”值）的时间段内迭代：t0，t1，…
在每一轮，青蛙从最初的河岸开始。对于一个给定的青蛙位置，最远的“跳到”位置是根据青蛙的最大可能跳跃距离和该范围内的石头的当前状态来计算的。如果找到这样一个有效的跳转到位置（即跳转到位置的值为零），则该过程重复，直到青蛙在另一个河岸上。
如果找不到跳跃（即，不存在和/或被覆盖的石头阻碍进展），石头“覆盖”水平递减一。然后，新的一轮开始了。