MC202 EF - Atividade de Laboratório no. 2

 

Descrição do Problema

Dada a função recursiva apresentada a seguir, escrever a versão não recursiva da mesma, fazendo uso de uma pilha
explícita, conforme explicado em sala (apresentação). A função dada visa encontrar todos os caminhos num 'labirinto' representado por uma matriz onde cada elemento contém inicialmente um caracter que indica se a posição correspondente pode ou não ser utilizada como parte do caminho procurado. A função tem como parâmetro as
coordenadas dos pontos de origem e destino. 
/********************************************
  Tenta achar todos os caminhos possíveis no 'labirinto'
  representado pela matriz m (global).
  Parâmetros:
    i,j: coordenadas do 'ponto origem'
    di,dj: coordenadas do 'ponto destino'
    c: caracter utilizado para marcar o caminho
    (usa a matriz m global, que representa o labirinto)
********************************************/
void tenta(int i, int j, int di, int dj,char c){
  /* deslocamentos das células vizinhas à atual */
  int dx[8] = {-1,-1,-1, 0, 0, 1,1,1};
  int dy[8] = {-1, 0, 1,-1, 1,-1,0,1};
  int k;
  if(m[i][j] == ' '){      
    m[i][j] = c;
    if((i==di) &&(j==dj)) {
        m[i][j] = '+';  
        imprime(); 
    } else {
      for(k=0; k < 8; k++) tenta(i+dx[k],j+dy[k],di,dj,'.');
    }
    m[i][j] = ' ';      
  }    
}    


O programa completo 'labirinto.c'  deverá ser utilizado como ponto de partida para a atividade. Seu código contém as 
declarações necessárias, funções auxiliares e a função 'main()' que cria um caso de testes.  As únicas alterações
devem ser relativas a
  • substituição da função tenta() pela versão equivalente não recursiva.
  • inclusão das funções auxiliares para criação da pilha, inserção e remoção de elementos.
A pilha utilizada para eliminar a recursão poderá ser feita utilizando alocação sequencial ou alocação ligada.

Importante:

Neste programa, as chamadas recursivas ocorrem dentro de um comando 'for' onde o contador, k, varia de 0 a 7. Ao eliminar a recursão através do uso de uma pilha, as 'operações' devem ser empilhadas em ordem inversa à que ocorrem na versão recursiva. Sendo assim, é recomendável que o empilhamento dessas operações seja feito em ordem inversa, ou seja, com o contador variando de 7 a 0.

Entradas

O programa gera seus próprios dados de teste, portanto não tem nenhuma entrada.

Saídas

As saídas do programa modificado devem ser exatamente as mesmas do programa original.

Data Limite para Entrega

O projeto deverá ser entregue por email ao assistente de ensino (gabriel@las.ic.unicamp.br)  até o dia 23/08/08
(o título do email deve iniciar com "[MC202]" para que seja facilmente identificável).