O labirinto e o minotauro perdido

Considere um labirinto como o do desenho abaixo:

Um labirinto desses pode ser representado por uma matriz retangular $L$, cujo elemento $L_{ij}$ vale 0 ou $-1$ conforme a casa correspondente do labirinto seja uma passagem livre ou uma parede, respectivamente.

Suponha agora que em alguma posição desse labirinto haja um minotauro perdido, e também uma porta (de entrada/saída). Como bons samaritanos, queremos ajudar o minotauro a encontrar a porta.

Um método geral para resolver esse problema consiste em marcar com o número $k$ ($k=1,2,\ldots$) as casas livres que estejam a exatamente $k - 1$ passos de distância da porta, pelo caminho mais curto possível. Suponha que, a cada passo, o minotauro possa se deslocar de apenas uma casa na vertical ou na horizontal. Então, rotula-se inicialmente a posição da porta com 1 e para cada $k \geq 2$ examinam-se todas as casas livres do labirinto, marcando-se com $k$ aquelas ainda não marcadas e que sejam vizinhas a alguma casa marcada com $k - 1$.

A marcação continua até ser atingido um valor de $k$ (28 no exemplo abaixo) tal que nenhuma casa esteja em condições de ser marcada. Supondo que a $L=[1\,.\,.\,6, 1\,.\,.\,11]$,² e que a porta esteja na posição $[6,11]$,³ ao final da marcação teremos a seguinte matriz:

Tendo feito esta marcação, um caminho mais curto do minotauro até a porta (se existir) pode ser determinado partindo-se da posição do minotauro e passando a cada etapa para uma casa vizinha cuja numeração seja menor do que a atual.

Por exemplo, se o minotauro estiver na posição $[3,2]$, este precisará percorrer pelo menos 25 casas para chegar à porta: $[3,2]$, $[3,1]$, $[4,1]$, $[5,1]$, $[5,2]$, $[5,3]$, $\dots\;$, $[4,10]$, $[4,11]$, $[5,11]$, $[6,11]$.