OpenEuphoria

RE: pathing.

• Posted by rforno at tutopia.com Aug 23, 2002
• 430 views

Mistertrik:
By a lucky coincidence, I posed a labirynth problem to my pupils in a C/C++
course I am giving at an University here in Argentina. Below you will find
two solutions to the problem, not much different from your problem. The
labirynth is a 0 - 1 matrix where a 1 allows passage. Movents are only
right - left - up - down. The programs are written basically in C, with only
I/O in C++. You will find easy translating them to Euphoria. The first and
shortest one is recursive. Sorry for the comments in Spanish.
Regards.

RECURSIVE SOLUTION:

// Programa para resolver un laberinto de F * C. Solucion recursiva.
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#define F 12
#define C 12
#define LAST C - 1
// Variables globales
char lab[F][C]; // Laberinto
char mat[F][C]; // Matriz correspondiente al camino mas corto
int camino[F * C][2]; // Camino(s)
int mascorto[F * C][2]; // El camino mas corto
int donde; // Los pasos dados por Teseo en ese camino
long cuenta; // Cantidad de caminos encontrados
int min; // La menor longitud de camino

// Rutina de ingreso de datos
void ingreso()
{
 int i, j;
 char c;
 ifstream datos;
 datos.open("laberint.txt");;
 if (! datos)
 {
  cout << "\nNo se pudo abrir el archivo de entrada laberint.txt\n";
  exit(1);
 }
 for (i = 0; i < F; i++)
  for (j = 0; j < C; j++)
  {
   datos >> c;
   if (c != '0' && c != '1')
   {
    cout << "\nDato incorrecto: " << c << endl;
    exit(2);
   }
   lab[i][j] = c;
  }
 datos.close();
}

// Rutina para mostrar el camino y guardar el mas corto
void mostrar_camino()
{
 int i, j;
 cuenta++; // Otro camino
 cout << "\nCamino encontrado:\n";
 for (i = 0; i <= donde; i++) // Mostrar camino
  cout << "[" << camino[i][0] << "," << camino[i][1] << "] ";
 cout << endl;
 cout << "Longitud: " << (donde + 1) << endl;
 cout << "Matriz resultante:\n";;
 for (i = 0; i < F; i ++) // Mostrar matriz resultante
 {
  for (j = 0; j < C; j++)
   cout << lab[i][j];
  cout << endl;
 }
 if (donde < min) // Si la longitud es menor
 {
  min = donde;
  for (j = 0; j <= donde; j++) // Copiar camino
  {
   mascorto[j][0] = camino[j][0];
   mascorto[j][1] = camino[j][1];
  }
  for (i = 0; i < F; i ++) // Copiar laberinto
   for (j = 0; j < C; j++)
    mat[i][j] = lab[i][j];
 }
}

// Rutina recursiva para buscar caminos
void buscar(int i, int j)
{
 if (i < F && j < C && i >= 0 && j >= 0 && '1' == lab[i][j]) // Si sigue
 {
  lab[i][j] = '+'; // Marcar senda usada
  camino[donde][0] = i; // Indicar el camino
  camino[donde][1] = j;
  if (LAST == j) // Fin del camino
   mostrar_camino();
  donde++; // Paso siguiente
  buscar(i + 1, j); // Hacia abajo
  buscar(i - 1, j); // Hacia arriba
  buscar(i, j + 1); // Hacia la derecha
  buscar(i, j - 1); // Hacia la izquierda
  donde--; // Retroceder un paso
  lab[i][j] = '1'; // Restaurar marca de senda
 }
}

void main()
{
 int i, j;
 ingreso();
 cuenta = 0; // Aun no hay caminos
 donde = 0; // Empezamos por el principio...
 min = F * C; // Valor inicial de la longitud menor
 for (i = 0; i < F; i++) // Buscar comienzo(s)
  if ('1' == lab[i][0])
   buscar(i, 0);
 cout << "\nSe encontraron " << cuenta << " caminos\n";
 if (cuenta) // Si hubo algun camino
 {
  donde = min; // Restaurar al camino minimo
  for (j = 0; j <= donde; j++)
  {
   camino[j][0] = mascorto[j][0];
   camino[j][1] = mascorto[j][1];
  }
  for (i = 0; i < F; i++) // Restaurar la matriz
   for (j = 0; j < C; j++)
    lab[i][j] = mat[i][j];
  cout << "\nEl camino mas corto fue:\n";
  mostrar_camino();
 }
 cout << "\nFin del programa\n";
}

NON-RECURSIVE SOLUTION:

// Programa para resolver un laberinto de F * C. Solucion no recursiva.
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#define F 12
#define C 12
#define LAST C - 1
// Variables globales
char lab[F][C]; // Laberinto
char mat[F][C]; // Matriz correspondiente al camino mas corto
int camino[F * C][2]; // Camino(s)
int ruta[F * C]; // Ultima ruta seguida
int mascorto[F * C][2]; // El camino mas corto
int donde; // Los pasos dados por Teseo en ese camino
long cuenta; // Cantidad de caminos encontrados
int min; // La menor longitud de camino

// Rutina de ingreso de datos
void ingreso()
{
 int i, j;
 char c;
 ifstream datos;
 datos.open("laberint.txt");;
 if (! datos)
 {
  cout << "\nNo se pudo abrir el archivo de entrada laberint.txt\n";
  exit(1);
 }
 for (i = 0; i < F; i++)
  for (j = 0; j < C; j++)
  {
   datos >> c;
   if (c != '0' && c != '1')
   {
    cout << "\nDato incorrecto: " << c << endl;
    exit(2);
   }
   lab[i][j] = c;
  }
 datos.close();
}

// Rutina para mostrar el camino y guardar el mas corto
void mostrar_camino()
{
 int i, j;
 cuenta++; // Otro camino
 cout << "\nCamino encontrado:\n";
 for (i = 0; i <= donde; i++) // Mostrar camino
  cout << "[" << camino[i][0] << "," << camino[i][1] << "] ";
 cout << endl;
 cout << "Longitud: " << (donde + 1) << endl;
 cout << "Matriz resultante:\n";;
 for (i = 0; i < F; i ++) // Mostrar matriz resultante
 {
  for (j = 0; j < C; j++)
   cout << lab[i][j];
  cout << endl;
 }
 if (donde < min) // Si la longitud es menor
 {
  min = donde;
  for (j = 0; j <= donde; j++) // Copiar camino
  {
   mascorto[j][0] = camino[j][0];
   mascorto[j][1] = camino[j][1];
  }
  for (i = 0; i < F; i ++) // Copiar laberinto
   for (j = 0; j < C; j++)
    mat[i][j] = lab[i][j];
 }
}

// Rutina auxiliar para buscar caminos
void buscar1(int i, int j)
{
 if (i < F && j < C && i >= 0 && j >= 0 && '1' == lab[i][j]) // Si sigue
 {
  donde++; // Un paso mas
  camino[donde][0] = i; // Indicar camino
  camino[donde][1] = j;
  ruta[donde] = 0; // Primer caso
  lab[i][j] = '+'; // Marcar senda
  if (LAST == j) // Si llega a la meta
   mostrar_camino();
 }
}

// Rutina inicial para buscar caminos
void buscar(int i, int j)
{
 int k;
 donde = 0; // Empezamos por el principio...
 camino[0][0] = i; // Punto inicial
 camino[0][1] = j;
 lab[i][0] = '+';
 ruta[0] = 0;
 while (donde >= 0) // Mientras queden sendas por recorrer
 {
  i = camino[donde][0]; // Ver donde estabamos
  j = camino[donde][1];
  k = ruta[donde];
  ruta[donde]++; // Proximo paso
  switch (k)
  {
   case 0:
    buscar1(i + 1, j); // Hacia abajo
    break;
   case 1:
    buscar1(i - 1, j); // Hacia arriba
    break;
   case 2:
    buscar1(i, j + 1); // Hacia la derecha
    break;
   case 3:
    buscar1(i, j - 1); // Hacia la izquierda
    break;
   default:
    lab[i][j] = '1'; // Restaura celda. Si llega aca, debe haber sido '1'
    donde--; // No hay mas posibilidades
    break;
  }
 }
}

void main()
{
 int i, j;
 ingreso();
 cuenta = 0; // Aun no hay caminos
 min = F * C; // Valor inicial de la longitud menor
 for (i = 0; i < F; i++) // Buscar comienzo(s)
  if ('1' == lab[i][0])
   buscar(i, 0);
 cout << "\nSe encontraron " << cuenta << " caminos\n";
 if (cuenta) // Si hubo algun camino
 {
  donde = min; // Restaurar al camino minimo
  for (j = 0; j <= donde; j++)
  {
   camino[j][0] = mascorto[j][0];
   camino[j][1] = mascorto[j][1];
  }
  for (i = 0; i < F; i++) // Restaurar la matriz
   for (j = 0; j < C; j++)
    lab[i][j] = mat[i][j];
  cout << "\nEl camino mas corto fue:\n";
  mostrar_camino();
 }
 cout << "\nFin del programa\n";
}
----- Original Message -----
From: <mistertrik at hotmail.com>
To: EUforum <EUforum at topica.com>
Sent: Thursday, August 22, 2002 10:43 PM
Subject: pathing.


>
> example of problem:
>
> sequence maze = {
> {5,5,5,5,5,5,5,5,5,5,5,5},
> {5,0,0,0,0,0,0,0,0,0,0,5},
> {5,0,0,0,0,5,0,0,0,0,0,5},
> {5,1,0,0,0,5,0,0,0,0,0,5},
> {5,0,0,0,0,5,0,0,0,9,0,5},
> {5,5,5,5,5,5,5,5,5,5,5,5}}
>
> How do I find a path to go from the 1 to the 9, avoiding all non-5
elements?
> (assume that there is only 1 1 and only 1 9, and their locations are known
> in advance)
> =====================================================
> .______<-------------------\__
> / _____<--------------------__|===
> ||_    <-------------------/
> \__| Mr Trick
>
>
>
>