function fibFrog(array $a): int
{
    $size = count($a);

    $fib = [0, 1];
    for ($i = 1; $fib[$i] <= $size;) {
        $i++;
        $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
    }

    $paths = [
        [
            'idx' => -1,
            'jmp' => 0
        ]
    ];

    $steps = array_fill(0, $size, false);

    while (count($paths) > 0) {
        $path = array_shift($paths);
        for ($i = count($fib) - 1; $i >= 2; $i--) {
            $idx = $path['idx'] + $fib[$i];
            if ($idx === $size) {
                return $path['jmp'] + 1;
            }
            if ($idx > $size
                || $steps[$idx]
                || $a[$idx] === 0
            ) {
                continue;
            }
            if ($a[$idx] === 1) {
                $steps[$idx] = true;
                $paths[]     = [
                    'idx' => $idx,
                    'jmp' => $path['jmp'] + 1
                ];
            }
        }
    }

    return -1;
}