Block Dude

Em Block Dude, o personagem principal pode subir caixas, mas apenas quando elas estão empilhadas de uma maneira específica que permite que ele as suba uma de cada vez. Mais especificamente, ele só pode SUBIR ou DESCER uma caixa por vez.

Considere que 1s representam as caixas e que 0 representa o fundo. Escreva uma função que retorne true se block dude puder atravessar a tela do lado esquerdo até o lado direito dadas as suas restrições.

Por exemplo, o layout de amostra abaixo deve retornar true.

[
  [0, 0, 0, 0, X, 0, 0, 0, 0],
  [0, 0, 0, X, 1, X, X, 0, 0],
  [0, X, X, 1, 1, 1, 1, X, 0],
  [X, 1, 1, 1, 1, 1, 1, 1, X]
]

block dude consegue atravessar essas caixas (observe que os X servem apenas para mostrar o caminho e não fazem parte da entrada real). Por outro lado:

[
  [0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 0, 0, 0, 0],
  [0, X, X, 1, 1, 1, 1, 0, 0],
  [X, 1, 1, 1, 1, 1, 1, 1, 0]
]

Deve retornar false, pois block dude fica preso na coluna 3, sem conseguir subir 2 caixas de uma vez.

Exemplos

can_traverse([
  [0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 0, 0, 1, 0, 0],
  [0, 1, 1, 1, 1, 1, 1, 1, 0]
]) ➞ false

# Block dude can't jump down 2 blocks.

can_traverse([
  [0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 0, 1],
  [0, 0, 1, 1, 1, 0, 1, 1, 1],
  [0, 1, 1, 1, 1, 1, 1, 1, 1]
]) ➞ true

# Note: Sometimes the exit is at the top!

can_traverse([
  [0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 1, 1, 1, 0, 0],
  [0, 1, 1, 1, 1, 1, 1, 1, 0]
]) ➞ true

can_traverse([
  [0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 1, 0, 0],
  [0, 1, 1, 1, 1, 1, 1, 1, 0]
]) ➞ false

# Block dude can't climb 2 blocks.

Observações

Consulte a aba Recursos para encontrar um link para jogar Block Dude.