function fibFrog(a: number[]): number {
  const size = a.length;

  const fib: number[] = [0, 1];
  for (let i = 1; fib[i] <= size; ) {
    i++;
    fib[i] = fib[i - 1] + fib[i - 2];
  }

  type Path = { idx: number; jmp: number };
  const paths: Path[] = [{ idx: -1, jmp: 0 }];
  const steps: boolean[] = new Array(size).fill(false);

  while (paths.length > 0) {
    const path = paths.shift() as Path;
    for (let i = fib.length - 1; i >= 2; i--) {
      const 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.push({ idx, jmp: path.jmp + 1 });
      }
    }
  }

  return -1;
}