Labirintos

[davidecom]

Olá, estou aprendendo programação em C e tenho que resolver um problema que envolve recursividade e alocação dinâmica. Vou definir o problema e abaixo. 

Gostaria apenas de uma orientação sobre como modelar a função recursiva que analisa se há algum caminho, a saída dessa função é apenas sim/nao.

 

Definição do problema:

Tenho que implementar um programa para determinar se existe pelo menos um caminho entre uma entrada E e uma saída S de um labirinto expresso através de uma matriz, conforme descrição da entrada a seguir.

 

Restrições

-Não são permitidos movimentos diagonais, ou seja, os movimentos permitidos são: Direita, Esquerda, Acima e Abaixo.

 

-A matriz não é “circular”, ou seja, não são permitidos movimentos entre as extremidades, por exemplo, não é permitido o movimento

da célula (0,0) para a célula (0,N-1), onde (L,C) representa a célula da linha L e coluna C e N a dimensão da matriz.

 

Entrada

 

A entrada começa com um inteiro na primeira linha, L, representando o número de labirintos a serem explorados. A seguir serão definidos cada labirinto seguindo o padrão: na primeira linha é definido N, que representa a dimensão da matriz (NxN); nas N linhas seguintes é definida a matriz, composta pelos sequintes símbolos: 0 - célula para trânsito livre; 1 - célula parede, não pode ser acessada; E - célula de entrada; e S - célula de saída.

 

ex.: 

2

 

8

1 1 1 1 1 0 0 0

1 0 0 0 1 0 0 0

1 E 1 1 1 0 0 0

1 0 0 0 1 1 1 1

1 0 1 0 0 0 0 1

1 0 0 0 1 0 0 1

1 1 1 1 1 0 S 1

0 0 0 0 1 1 1 1

 

7

1 1 1 1 1 0 0

1 0 E 0 0 0 0

1 1 1 1 1 0 0

1 0 0 0 1 1 0

1 0 1 0 0 0 1

1 S 0 0 1 0 0

1 1 1 1 1 0 0