labirinto

15/05/2007

2

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.



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 */



Responder

Posts

17/05/2007

Relfi

niguém?


Responder