Navegação no Jardim Labirinto

No parque botânico de Nlogônia foi recentemente construído um vasto Jardim Labirinto — uma atração composta por linhas e colunas de caminhos formados por arbustos. O objetivo é simples: sair do portão de entrada, localizado no canto superior esquerdo do jardim ($[0,0]$), e cruzar o labirinto até a saída, situada no canto inferior direito.

Porém, nem tudo são flores! Em certas partes do labirinto, trechos estão obstruídos por trepadeiras espinhosas, que dificultam a caminhada. O visitante deve escolher seu trajeto com sabedoria, pois, a cada obstáculo vencido, está sujeita a arranhões.

O visitante pode realizar movimentos apenas para leste, oeste, norte ou sul (nunca na diagonal). Seu objetivo: descobrir a rota da entrada à saída que passa pelo menor número possível de obstáculos. Os pontos de entrada e saída nunca estão bloqueados.

Entrada

• A primeira linha contém um inteiro $N$ ($2 \leq N \leq 100$), representando as dimensões do jardim (ele é um quadrado $N\times N$);
• As $N$ linhas seguintes trazem cada uma $N$ inteiros, onde $0$ representa um caminho livre e $1$ representa um quadrado bloqueado por trepadeiras espinhosas.

Saída

Imprima uma linha com um único inteiro: o menor número de trechos bloqueados que precisam ser atravessados para cruzar do portão de entrada até a saída do jardim.

Exemplos

Exemplo de entrada 1

6
0 1 0 0 0 0
1 1 0 0 1 1
1 0 1 1 1 1
0 0 0 1 1 0
0 0 1 1 1 0
0 1 0 0 0 0

Exemplo de saída 1

3

Exemplo de entrada 2

2
0 0
1 0

Exemplo de saída 2

0