lunes, 8 de noviembre de 2010

Laberintos

Este problema se trata de escribir un programa que resuelva un laberinto hallando el camino mínimo desde la salida a la meta.

Las especificaciones son las siguientes:

Se recibe como entrada un laberinto que es una matriz de H filas y W columnas donde cada elemento es una casilla del laberinto.

Para resolver el laberinto hay que llegar de la salida a la meta moviéndose solo a través de las casillas despejadas (sin atravesar muros). En cada movimiento se puede avanzar una única casilla hacia arriba, abajo, izquierda o derecha; pero no se puede mover en diagonal.

El programa debe calcular el mínimo numero de movimientos que hacen falta para llegar de la salida a la meta.

Formato de entrada:

  • En la primera linea se recibe un entero W (0 <= W <= 50) que representa el numero de columnas del laberinto.
  • En la segunda linea se recibe un entero H (0 <= H <= 50) representando el numero de filas.
  • En las siguientes H lineas, una representacion de las casillas de cada fila, por orden. Cada fila se representa con una cadena de W caracteres donde cada caracter representa una casilla del laberinto codificada de la siguiente manera:
    • El caracter 'S' significa que es la casilla de salida y solo aparece una vez en todo el laberinto.
    • El caracter 'M' significa que es la casilla de meta y solo aparece una vez en todo el laberinto.
    • El caracter '.' representa una casilla despejada.
    • El caracter '#' representa una casilla que es un muro.

Formato de salida:

El programa debe imprimir una linea con el numero de pasos mínimo para resolver el laberinto. Si el laberinto no tiene solución deberá imprimir una linea conteniendo la palabra "imposible" (sin comillas).

Ejemplo de entrada:
6
5
S#...#
.#.#.#
.###..
.#.##.
...#M.

Ejemplo de salida:
imposible

Solución:

La solución que propongo a continuación hace uso del algoritmo de Dijkstra para encontrar el camino mínimo en un grafo desde un nodo origen a un nodo destino.

El algoritmo de Dijkstra funciona más o menos así:

  1. Se asigna a todos los nodos una distancia acumulada igual a infinito. Excepto al nodo inicial que tiene distancia acumulada 0.
  2. Partiendo del nodo inicial, se calcula la distancia acumulada hacia cada uno de sus nodos adyacentes no marcados. Si alguno de estos ya tiene una distancia acumulada se reemplazara únicamente si la nueva distancia es menor. La distancia acumulada de un nodo es igual a la distancia acumulada del nodo inicial mas el costo de la arista que los une.
  3. Se marca el nodo inicial.
  4. Se escoge como nuevo nodo inicial el nodo no marcado con menor distancia acumulada.
  5. Se repiten los pasos 2, 3 y 4 mientras existan nodos no marcados.
Al final la distancia acumulada de cada nodo sera la mínima distancia para llegar a él partiendo desde el nodo inicial.

Para la solución, representaremos el laberinto como una matriz de enteros. Donde cada celda de la matriz representara un nodo del grafo. La salida, la meta y las posiciones despejadas tendrán el valor 0 y los muros el valor -1. Los nodos adyacentes a otro nodo (celda) serán las celdas que se encuentren arriba, abajo, a su izquierda y a su derecha. También se guardaran las coordenadas (fila y columna) de las celdas de salida y meta a fin de identificarlas. Se considera que el costo para ir de un nodo a otro adyacente sera siempre 1.

Considerando lo anterior, paso a describir el algoritmo:

  1. Se asigna a todas las celdas 0 como distancia acumulada. Excepto a los muros que es -1.
  2. Si las coordenadas de la celda de salida son iguales a las coordenadas de la meta no se hace nada.
  3. Sino, partiendo de las coordenadas de la celda de salida, se calcula la nueva distancia acumulada a cada uno de sus "nodos" adyacentes. La nueva distancia acumulada sera el valor contenido en la celda de salida más 1. El valor de los nodos (celdas) adyacentes se actualiza con la nueva distancia únicamente si es 0 o es mayor que la nueva distancia.
  4. Se toma como nuevos nodos de salida las celdas que fueron actualizadas.
  5. Se repiten los pasos 2, 3 y 4 recursivamente para cada nueva celda de salida.

Al terminar la ejecución, se tendrá en la celda de meta el mínimo numero de pasos para llegar ahí partiendo de la celda de salida. Si el laberinto no tiene solución, la casilla de meta contendrá un 0.

Implementación:
#include <stdio.h>
#include <stdlib.h>

void resolver(int fs, int cs, int fm, int cm, int **l, int f, int c) {
 int x, y, d=l[fs][cs] + 1;
 
 if(fs == fm && cs == cm) return; //se llega a la meta
 
 for(int i=1; i<=4; i++) {
  switch(i) {
   case 1: x=cs-1; y=fs; break; //camino 1
   case 2: x=cs; y=fs-1; break; //camino 2
   case 3: x=cs+1; y=fs; break; //camino 3
   case 4: x=cs; y=fs+1; break; //camino 4
  }
  if(x>=0 && x<c && y>=0 && y<f) {
   //si se mejora la distancia o la casilla no se ha visitado
   if(l[y][x]>d || l[y][x]==0) {
    l[y][x] = d;
    resolver(y, x, fm, cm, l, f, c);
   }
  }
 }
}

int main() {
 int c, f, **l;
 int fs, cs, fm, cm;
 scanf("%d\n%d\n", &c, &f);
 l = new  int *[f];
 for(int i=0; i<f; i++) {
  l[i] = new int [c];
  char a;
  scanf("%c", &a);
  for(int j=0; a!='\n'; j++) {
   switch(a) {
    case '#': //muro
     l[i][j] = -1;
     break;
    case '.': //camino
     l[i][j] = 0;
     break;
    case 'S': //salida
     l[i][j] = 0;
     fs = i; cs = j; //coordenadas de la salida
     break;
    case 'M': //meta
     l[i][j] = 0;
     fm = i; cm = j; //coordenadas de la meta
     break;
   }
   scanf("%c", &a);
  }
 }
 resolver(fs, cs, fm, cm, l, f, c);
 if(l[fm][cm] > 0) {
  printf("%d\n", l[fm][cm]);
 } else {
  printf("imposible\n");
 }
 return 0;
}

Saludos.

No hay comentarios:

Publicar un comentario