Pulo do Gato

O gato Obinho gosta de brincar no pátio do colégio, que tem a forma de um quadriculado de L linhas por C colunas de lajotas, que podem ser brancas ou pretas. Obinho está na lajota inicial, na linha 1, coluna 1 (canto superior esquerdo), e quer ir pulando até a lajota final, na linha L, coluna C (canto inferior direito). Mas ele só gosta de pular de uma lajota preta para outra lajota preta, nunca pisando numa lajota branca. Além disso, ele não consegue pular muito longe. A parte esquerda da figura mostra as lajotas que o Obinho pode alcançar com um pulo: qualquer lajota dentro do quadrado de 5 x 5 lajotas centrado na posição atual dele.

Obinho quer chegar na lajota final com o número mínimo de pulos possível. Por exemplo, na parte direita da figura, para L=10 e C=14, o menor número de pulos possível é 11. Seu programa deve computar o número mínimo de pulos para o Obinho chegar na lajota final!

Entrada

A primeira linha da entrada contém dois inteiros L e C, representando o número de linhas e colunas do pátio. As L linhas seguintes contêm, cada uma, C inteiros indicando a cor das lajotas: 1 para preta; 0 para branca.

Saída

Imprima uma linha contendo o número mínimo de pulos que o gato Obinho precisa dar para ir da lajota inicial até a lajota final. Se não for possível pular até a lajota final, imprima -1.

Restrições

• 1 ≤ L,C ≤ 500;
• As lajotas inicial e final são sempre pretas.

Informações sobre a pontuação

• Para um conjunto de casos de teste valendo 10 pontos, L=1 e todas as lajotas são pretas;
• Para um conjunto de casos de teste valendo 10 pontos, L=1;
• Para um conjunto de casos de teste valendo 10 pontos, L>1, C>1 e todas as lajotas são pretas;
• Para um conjunto de casos de teste valendo 20 pontos, L ≤ 100 e C ≤ 100.

Exemplos

10 14
1 0 0 0 1 1 0 0 1 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0 1 0 1 0 1 1
0 0 1 0 0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1 0 0 0 0 0 1

11
	

10 14
1 0 0 0 1 1 0 0 1 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0 0 0 1 0 1 1
0 0 1 0 0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1 0 0 0 0 0 1

-1
	

1 12
1 1 1 1 1 1 1 1 1 1 1 1

6