一.问题描述

1. 一只青蛙正在过河。 河流分为x个单位，每个单位可能存在或不存在石头。 青蛙可以跳到石头上，但不能跳入水中。

2. 给出按照升序排序的石块位置（单位），确定青蛙是否能够通过落在最后一块石头上过河。 最初，青蛙在第一块石头上并假设第一次跳跃必须是1个单位。

3. 如果青蛙的最后一次跳跃是k个单位，那么它的下一个跳跃必须是k-1，k或k + 1个单位。 请注意，青蛙只能向前

* 石头的数量 > 0 & <1,100
* 每个石头的位置都是非负整数 <  2^31
* 第一块石头的位置始终为0。

Example 1:
[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:
[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

二.代码实现

#include"stdlib.h"
#include"stdio.h"

#define MAX_LEN 1100

bool canCrossedByStep(int* stones, int stonesSize,int i,int j,int curStep);
bool canCross(int* stones, int stonesSize);
bool canCross(int* stones, int stonesSize) {
    if(stonesSize < 2)
    {
        return true;
    }
    if(stones[0] != 0 || stones[1] != 1)
    {
        return false;
    }
    return canCrossedByStep(stones, stonesSize,1,2, 1);
    
}

//i当前所在的位置，j寻找下一步的开始位置,curStep当前步长
bool canCrossedByStep(int* stones, int stonesSize,int i,int j,int curStep)
{
    if (j == stonesSize)
    {
        return true;
    }

    for (int k = j; k < stonesSize; ++k)
    {
        //已跳不过去，因为stones[index] > stones[k](index > k)
        if (stones[k] > stones[i] + curStep + 1)
        {
            return false;
        }
        else if (stones[k] == stones[i] + curStep + 1)
        {
            //后面不可能再跳过去了，可以直接return
            //printf("stones[j] == stones[i] + curStep + 1,stones[i]:%d,stones[j]:%d,step:%d\n",stones[i],stones[k],curStep + 1);
            return canCrossedByStep(stones, stonesSize,k,k+1,curStep + 1);
        }
        else if (stones[k] == stones[i] + curStep)
        {
            //printf("stones[j] == stones[i] + curStep,stones[i]:%d,stones[j]:%d,step:%d\n",stones[i],stones[k],curStep);
            if(canCrossedByStep(stones, stonesSize,k,k+1,curStep))
            {
                return true;
            }
        }
        else if (curStep - 1 > 0 && stones[k] == stones[i] + curStep - 1)
        {
            //printf("stones[j] == stones[i] + curStep - 1,stones[i]:%d,stones[j]:%d,step:%d\n",stones[i],stones[k],curStep - 1);
            if(canCrossedByStep(stones, stonesSize,k,k+1,curStep - 1))
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    // int a[] = {0,1,3,5,6,8,12,17};
    // int b[] = {0,1,2,3,4,8,9,11};

    while(true){
        int buf[MAX_LEN];
        int index = 0;
        printf("please input array,limited length 1100:\n");
        while(scanf("%d",&buf[index]) && buf[index] >= 0){
           // printf("%d\n",buf[index]);
            ++index;
            if (index >= 1100)
            {
                break;
            }
        }
        printf("length:%d\n", index);
        printf("the result is:%d\n",canCross(buf,index));
    }
    return 1;
}

三.测试结果

image.png