Array
(
)

labirinto

Relfi
   - 15 mai 2007

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.

#Código




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
   - 17 mai 2007

niguém?