Ajuda Laberinto

[Lilith! 13]

Olá amigos da WC. Estou com uma dificuldade em meu programa.

O proposito dele é ler uma matriz labirinto e imprimir a saída do tal labirinto.

a matriz é dada por # e 0, onde 0 são os caminhos livres.

Ela sempre ira começar na matriz[0][0] e terminar na matriz[n-1][m-1];

O programa esta funcional, contudo se a matriz for maior que 5 ele buga e eu preciso que ele funcione para uma matriz 20x20.

 

segue o programa:

/* Bibliotecas a serem acessadas e definição do que é parede e caminho livre */

#include <stdio.h>

#include <stdlib.h>

#define CAMINHO '0'

#define PAREDE '#'

#include<windows.h>

#include<windows.h>

char **aloca(int n, int m);

void libera(int n, char **v);

void labirinto(int n, int m, char **lab);

 

 

/*definicoes da estrutura da PILHA com a estrutura de um elemento da pilha que contem as coordenadas do ponto salvo (i,j) e tambem quais vizinhos ja foram visitados */

typedef struct pilha_tipo

{

int i,j;

int k;

struct pilha_tipo *next;

} pilha_t;

 

/* Inicializa a pilha no vazio*/

pilha_t *inic(){ return NULL; }

pilha_t *new(){ return (pilha_t *)malloc(sizeof(pilha_t)); }

 

/* coloca um elemento da pilha e verifica se ela esta ou não vazia*/

int empty(pilha_t *p){

if( p == NULL ) return 1;

return 0;

}

 

/* insere um elemento de valores (i,j,k) no fim da pilha, entao devolve o novo ponteiro para o fim da pilha */

pilha_t *push(pilha_t *p, int i, int j, int k){

pilha_t *novo = new();

 

novo->i = i;

novo->j = j;

novo->k = k;

 

if( empty(p) ) novo->next = NULL;

else novo->next = p;

 

return novo;

}

 

/* retira o elemento do topo da pilha, e devolve o novo topo da pilha*/

pilha_t *pop(pilha_t *p){

if( !empty(p) ){

pilha_t *aux = p->next;

free(p);

return aux;

}

else return NULL;

}

 

/* Salva informacoes do caminho percorrido nas variaveis */

void top(pilha_t *p, int *i, int *j, int *k){

if( !empty(p) )

{

*i = p->i;

*j = p->j;

*k = p->k;

}

}

 

/* devolve o numero de elementos na pilha e determinar quantos passos andou-se para chegar a algum ponto */

int num_pilha(pilha_t *p)

{

int n = 0;

while(p != NULL){

n++;

p = p->next;

}

return n;

}

 

/* Tipo de estrutura que salva um caminho percorrido, com suas posicoes (i,j) */

typedef struct caminho_tipo {

int i,j;

} caminho_t;

 

/* funcao que recebe uma pilha e vai salvando as informacoes de seus elementos em ordem contraria em um vetor alocaalocado

dinamicamente, para posterior impressao; devolve o ponteiro do inicio do vetor */

caminho_t *salva_caminho(pilha_t *p, int tam)

{

int i;

caminho_t *aux = (caminho_t *)malloc(tam*sizeof(caminho_t));

 

/* salva no vetor em ordem contraria */

for(i=tam-1 ; i>=0 ; i--){

aux.i = p->i;

aux.j = p->j;

/* vai para o proximo elemento na pilha */

p = p->next;

}

return aux;

}

 

 

/* aloca uma matriz de tamanho n x m, retornando

o ponteiro do comeco da matriz */

char **aloca(int n, int m)

{

int i;

char **v = (char **)malloc(n*sizeof(char *)); /* aloca um vetor de tipo ponteiro de ponteiros */

for(i=0 ; i<n ; i++) /* cada posicao do vetor aponta para um outro vetor alocado */

v = (char *)malloc(m*sizeof(char));

return v;

}

 

/* libera a memoria alocada por uma matriz de n linhas */

void libera(int n, char **v){

int i;

 

for(i=0 ; i<n ; i++) free(v); /* libera a memoria de cada vetor alocado */

free(v); /* libera a memoria do vetor ponteiro de ponteiros */

}

 

/* o codigo abaixo testa todos os caminhos que nao passem pelo mesmo ponto mais de uma vez e pega o menor deles

e utilizada uma matriz que indica se um determinado ponto ja foi visitado ou nao apos todas as chamadas, o ponto

é dito como nao visitado, assim ele pode ser utilizado em outros caminhos */

void labirinto(int n, int m, char **lab){

/* vai para esquerda com (a,b-1), direita com (a,b+1), baixo com (a-1,b) e para baixo com (a+1,b) */

const int di[] = { 0, 0,-1, 1};

const int dj[] = {-1, 1, 0, 0};

 

/* padrao utilizado para identificar quais lados ja foram visitados:

0 nenhum, 1 direita, 2 direita e esquerda, 3 direita esquerda e para baixo, 4 para os quatro cantos*/

int i,j, val, x, y, i3, j3;

int i2,j2, k;

char res[20][20];

 

pilha_t *pilha;

caminho_t *caminho = NULL; /* para salvar o vetor com o menor caminho */

int minimo; /* minimo de passos para chegar aa saida */

char **foi; /* matriz que indica se uma certa posicao ja foi visitada ou nao */

/* aloca foi */

foi = aloca(n,m);

 

/* zera foi torna enhum ponto visitado) */

for(i=0 ; i<n ; i++)

{

for(j=0 ; j<m ; j++)

{

foi[j] = 0;

}

}

 

 

/* minimo = -1 e um padrao para indicar que nao foi encontrado menor caminho */

minimo = -1;

 

/* inicializa a pilha e insere um elemento (0,0) sendo que nenhum dos vizinhos foi visitado */

pilha = inic();

pilha = push(pilha, 0,0,0);

 

/* enquanto a pilha tiver elementos, ou seja, enquanto houverem caminhos a serem percorridos */

while( !empty(pilha) ){

/* pega os valores do elemento do topo da pilha */

top(pilha, &i,&j,&k);

val = num_pilha(pilha); /* conta o numero de passos para chegar ate ali */

foi[j] = 1; /* marca o ponto como visitado */

 

/* se o ponto atual for o ponto de destino (n-1,m-1) */

if(i==n-1 && j==m-1){

/* e o caminho obtido for o primeiro ou menor que o anterior */

if(minimo==-1 || minimo>val){

/* elimina o caminho antigo e salva o atual */

minimo = val;

free(caminho);

caminho = salva_caminho(pilha, minimo);

}

}

else{

/* senao, continua a visitar os vizinhos, comecando do primeiro que ainda nao visitou, 4 pois só á quatro direções */

for( ; k<4 ; k++){

/* pega suas coordenadas */

i2 = i+di[k];

j2 = j+dj[k];

 

/*atualiza valor do elemento da pilha*/

pilha = pop(pilha);

pilha = push(pilha, i,j,k+1);

 

/*insere mais um elemento na pilha*/

if(i2<0 || j2<0 || i2>=n || j2>=m || foi[i2][j2]) continue; /* caso nao de para inserir o elemento, pule */

if(lab[i2][j2]==CAMINHO && !foi[i2][j2]){

pilha = push(pilha, i2,j2,0);

break;

}

}

}

 

/* se algum elemento tiver sido inserido na pilha, nao elimina o atual */

if(i!=pilha->i || j!=pilha->j) continue;

foi[j] = 0;

pilha = pop(pilha);

}

 

/* libera a matriz foi */

libera(n, foi);

 

/* imprime a resposta */

for(i=0 ; i<minimo ; i++)

{

lab[caminho.i][caminho.j]='X';

}

for(i=0; i<n; i++)

{

for(j=0; j<m; j++){

printf("%c", lab[j]);

}

printf("\n");

}

 

/* libera o vetor com o caminho */

free(caminho);

}

 

int main(){

int n , m; /* Parametros para linhas e colunas usados nos testes com matrizes diferentes de 20x20*/

int i,j;

char **lab;

scanf("%d %d", &n, &m);

lab = aloca(n,m);

for(i=0 ; i<n ; i++)

{

for(j=0 ; j<m ; j++)

{

scanf(" %c", &lab[j]);

}

}

 

 

/* Chama a função para resolver o labirinto */

labirinto(n,m, lab);

 

/* libera a memoria alocada para evitar bugs */

libera(n, lab);

 

return 0;

}

[Inoxybel 51]

Se possível, edite seu tópico colocando a source dentro da tag PHP ou CODE