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
Entrada
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 |
Saída
11 |
Entrada
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 |
Saída
-1 |
Entrada
1 12 1 1 1 1 1 1 1 1 1 1 1 1 |
Saída
6 |