Seu programa

Faça um programa em C para resolver o seguinte problema:

Dados dois inteiros positivos $m$, $n$, uma matriz $L=[1\,.\,.\,m, 1\,.\,.\,n]$, representando um labirinto, a posição $[m1, m2]$ de um minotauro e a posição $[p1,p2]$ da porta desse labirinto, determinar (se existir) um caminho mais curto que o minotauro deve percorrer até encontrar a porta. O labirinto é uma matriz de inteiros cujos elementos são 0 ou $-1$, conforme a posição correspondente do labirinto seja uma passagem livre ou uma parede, respectivamente.

Se tal caminho não existir, o programa deve imprimir uma mensagem para que uma equipe de salvação vá urgentemente resgatar o minotauro.

O seu programa deve fazer uso de (pelo menos) duas funções, como descrito abaixo.

• Uma função com o protótipo

  
     void marque(int L[][MAXCOL], int m, int n, int p1, int p2);
  

  que tem como parâmetros um labirinto, isto é, uma matriz de inteiros $L=[1\,.\,.\,m, 1\,.\,.\,n]$, suas dimensões $m$ e $n$, e dois inteiros $p1$, $p2$ que indicam a posição $[p1,p2]$ da porta nesse labirinto.

  Essa função deve efetuar a marcação da matriz $L$, como explicado anteriormente. (Após a chamada dessa função, o seu programa deve imprimir essa matriz já marcada.)

• Uma outra função com o protótipo

  
     void imprima_caminho(int L[][MAXCOL], int m, int n, int m1, int m2);
  

  que tem como parâmetros uma matriz de inteiros $L[1\,.\,.\,m,1\,.\,.\,n]$ já marcada, as dimensões $m$, $n$ dessa matriz, e dois inteiros $m1$, $m2$ indicando a posição $[m1, m2]$ do minotauro nessa matriz.

  Esta função deve imprimir, caso exista, o caminho a ser percorrido pelo minotauro até a porta. Aqui, queremos a ordem em que as posições $[i,j]$ da matriz devem ser percorridas.

  Adicionalmente, para uma visualização melhor desse caminho no labirinto, essa função deve imprimir também um outro labirinto (matriz tipo char), onde apareçam caracteres apropriados indicando as paredes, as posições livres, a posição do minotauro (por exemplo, a letra M), a posição da porta (por exemplo, a letra P), e o caminho que o minotauro deve seguir.