labirinto
15/05/2007
0
Fala rapaziada beleza....?!
toh fazendo um programinha que é um labirinto. nelo o usuario entra com as coordenadas inicias e finais e o programa de veveria achar o caminho do ponto inicial para o ponto final...até aí beleza..td recursivo td bunitinho...
só que ele tah fazendo na maioria das vezes um caminho munto longo...andei peskisando e vi que tem mtas formas de se ecnotrar um caminhos ou um ponto numa matriz, e que existem mtas formas de busca...Mais grande parte delas usa de pilhas e filas...coisa que só por enquanto naum faço a menor idéia de como usar...Decobri um forma que considerei ser melhor que mtas outras no meu ponto de vista, onde vc parte do ponto final com k=0 e vai marcando com k+1 tdas as casas visinhas à atual, no final vc tem uma única série sequencial ligando o ponto final e o inicial, este é o caminho mais curto.
Ex.
toh fazendo um programinha que é um labirinto. nelo o usuario entra com as coordenadas inicias e finais e o programa de veveria achar o caminho do ponto inicial para o ponto final...até aí beleza..td recursivo td bunitinho...
só que ele tah fazendo na maioria das vezes um caminho munto longo...andei peskisando e vi que tem mtas formas de se ecnotrar um caminhos ou um ponto numa matriz, e que existem mtas formas de busca...Mais grande parte delas usa de pilhas e filas...coisa que só por enquanto naum faço a menor idéia de como usar...Decobri um forma que considerei ser melhor que mtas outras no meu ponto de vista, onde vc parte do ponto final com k=0 e vai marcando com k+1 tdas as casas visinhas à atual, no final vc tem uma única série sequencial ligando o ponto final e o inicial, este é o caminho mais curto.
Ex.
Matriz de caminho 111111111110111 100000000010101 101111111000001 101000000000001 101111111111101 100000101000101 101110101010101 101000101010101 111011101010101 000010001010101 100010101010101 100010101010101 101110101010101 100000100010001 111111111111111 Origem: (0,11) ; Destino: (9,0) Matriz de custos 225 225 225 225 225 225 225 225 225 225 225 0 225 225 225 225 13 12 11 10 9 8 7 6 5 225 1 225 5 225 225 14 225 225 225 225 225 225 225 4 3 2 3 4 225 225 15 225 11 10 9 8 7 6 5 4 3 4 5 225 225 16 225 225 225 225 225 225 225 225 225 225 225 6 225 225 17 18 19 20 21 225 45 225 27 26 25 225 7 225 225 18 225 225 225 22 225 44 225 28 225 24 225 8 225 225 19 225 25 24 23 225 43 225 29 225 23 225 9 225 225 225 225 26 225 225 225 42 225 30 225 22 225 10 225 30 29 28 27 225 41 42 41 225 31 225 21 225 11 225 225 30 29 28 225 40 225 40 225 32 225 20 225 12 225 225 31 30 29 225 39 225 39 225 33 225 19 225 13 225 225 32 225 225 225 38 225 38 225 34 225 18 225 14 225 225 33 34 35 36 37 225 37 36 35 225 17 16 15 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 Representacao do caminho minimo 11111111111.111 1.........1.101 1.1111111...001 1.1000000000001 1.1111111111101 1.....101000101 10111.101010101 101...101010101 111.11101010101 ...10001010101 100010101010101 100010101010101 101110101010101 100000100010001 111111111111111 Pensei em fazer da mesmo forma que fiz a busca ( com recursão), mas não está dando ceto, alguem pode me dar uma luz.... Meo código está assim ó... Pode ser usado este labirinto para teste. 11111111111111111111 10000001100000000011 11000001100000001011 11000001100000000011 11000001100000001011 11000111111000001011 11000000011000001011 11000000011111101011 11000000000001101001 11000000111101101011 11000000000000001011 11000001100000001011 11000111111000001011 11000000011000001011 11000001100000000011 11000001100000000011 11000000011111101011 11011101110110111011 11001100000000111011 11111111111111111111 Salva ele como lab20x20.txt no Bloco de notas no c: sem a função numerasaida ele funfa perfeito... Utilizo de Linguagem c++ no Turbo c++ Explorer faloww.... Desde já agradeço. #include<iostream.h> include<conio.h> include<stdio.h> include<stdlib.h> /* fun‡ao _exit(0) */ define col 63/* Define tamanho da Coluna do labirinto */ define lin 23/* Define tamanho da linha do labirinto */ //define saida 2 /* Define valor de saida */ //define boneco 3/* Define valor de Boneco ?????*/ unsigned char texto[1470];/* Guarda valores do Labirinto 1 */ int lab [col][lin];/* Labirinto */ char lab2[col][lin];/* enumera‡ao para busca ??????*/ int i,j,k,C_begin,L_begin,C_out,L_out,cont=0;/* i->COLUNA j->LINHA K->Contador p/ excluir \n ("carriage return=13 decimal-ASCII" e o "linfeed=10 decimal-ASCII" cont->contador da fun‡ao busca saida */ /* int C1=1; int L1=1; int C2=60; int L2=21; */ int fim=3; int inicio=4; int visitado=´x´; int volta=2; void carregalab()/* Come‡o da fun‡ao carrega labirinto */ { k=0; FILE *arq; if ((arq = fopen("c:\\lab20x20.txt","r")) == NULL)/*verifica se arquivo foi aberto*/ { cout<<"erro: Nao abriu o arquivo.";/* exibe caso erro encontrado*/ } else { if((fread(texto,sizeof(char),1470,arq)) == NULL)/* Lˆ arquivo caso aberto */ cout<<"erro: Nao foi possivel ler arquivo aberto."; else { for(j=0;j<23;j++) { for(i=0;i<63;i++) { if(texto[k]==´0´) /* Monta/Preenche vetor lab com valor na posi‡ao k vetor texto */ lab[i][j]=0; else { lab[i][j]=1; } k++; } k=k+1; /* Pula caracteres de enter*/ } } } } /*Fim da fun‡ao carrega labirinto */ void imprimelab() /* Come‡a fun‡ao imprime labirinto */ { //cout<<"\n\n\n\n\n\t-=LABIRINTO=-"; for(j=0;j<23;j++) { for(i=0;i<63;i++) { gotoxy(5+i,10+j); /* Centraliza na tela*/ if(lab[i][j]==0) /* Imprime na tela */ { cout<<" "; /* Ceta passagens livres */ } else if(lab[i][j]==visitado) cout<<"."; else if(lab[i][j]==3) cout<<"F"; else if(lab[i][j]==4) cout<<"I"; else if(lab[i][j]==2) cout<<" "; else cout<<"H";/* Ceta paredes */ } } } /* Fim da fun‡ao imprime labirinto */ int numerasaida(int C1, int L1, int C2, int L2, int cont)/* Come‡a fun‡ao busca sa¡da */ { lab[C2][L2]=cont; if(C2 == C1 && L2 == L1) { return (1); } if(lab[C2+1][L2] == 0) { cont=cont+1; if(numerasaida(C1, L1, C2+1, L2, cont)) { return (1); } } if(lab[C2][L2+1] == 0) { cont=cont+1; if(numerasaida(C1, L1, C2, L2+1, cont)) { return (1); } } if(lab[C2-1][L2] == 0) { cont=cont+1; if(numerasaida(C1, L1, C2-1, L2, cont)) { return (1); } } if(lab[C2][L2-1] == 0) { cont=cont+1; if(numerasaida(C1, L1, C2, L2-1, cont)) { return (1); } } return (0); } int buscasaida(int C1, int L1, int C2, int L2)/* Come‡a fun‡ao busca sa¡da */ { if(C1 == C2 && L1 == L2) { return (1); } if(lab[C1+1][L1] == lab[C1][L1]-1) { lab[C1][L1]=visitado; if(buscasaida(C1+1, L1, C2, L2)) { return (1); } } if(lab[C1][L1+1] == lab[C1][L1]-1) { lab[C1][L1]=visitado; if(buscasaida(C1, L1+1, C2, L2)) { return (1); } } if(lab[C1-1][L1] == lab[C1][L1]-1) { lab[C1][L1]=visitado; if(buscasaida(C1-1, L1, C2, L2)) { return (1); } } if(lab[C1][L1-1] == lab[C1][L1]-1) { lab[C1][L1]=visitado; if(buscasaida(C1, L1-1, C2, L2)) { return (1); } } return (0); } /*Fim da fun‡ao busca sa¡da */ void main() /* Main */ { clrscr(); carregalab(); imprimelab(); cout<<"\n\n\nDigite Coluna inicial: "; cin>>C_begin; cout<<"\nDigite Linha inicial: "; cin>>L_begin; cout<<"\nDigite Coluna de saida: "; cin>>C_out; cout<<"\nDigite Linha de saida: "; cin>>L_out; numerasaida(C_begin, L_begin, C_out, L_out, cont); if (buscasaida(C_begin, L_begin, C_out, L_out)) { cout<<"certo"; imprimelab(); lab[C_begin][L_begin]=inicio; lab[C_out][L_out]=fim; imprimelab(); } else cout<<"ret zero"; getch(); } /*Fim do main */
Relfi
Curtir tópico
+ 0
Responder
Posts
Clique aqui para fazer login e interagir na Comunidade :)