Cuando estaba en el primer curso de la facultad, hicimos una práctica en la asignatura Fundamentos de la Programación que consistía en resolver un laberinto almacenado en un fichero. Me gustó bastante hacer ese programa y lo comparto en el blog para los curiosos que quieran ver cómo funciona.



Formato del laberinto en el fichero

Los ficheros que almacenan el laberinto tienen el siguiente formato:

7 7
ppppppp
pellllp
plplppp
plplllp
plplppp
pllllsp
ppppppp

Donde:

Programa principal

Dado esto, es posible implementar un programa que lea el fichero, cree una matriz representando el laberinto e intente resolverlo. Esto se podría hacer con:

#include <iostream>
#include <vector>

#include "Laberinto.h"

using namespace std;

int main()
{
    unsigned int FIL, COL;
    cin >> FIL >> COL;

    Laberinto lab('+',' ','#',FIL,COL);
    lab.printLab();
    lab.resolverLaberinto();
    lab.printLabResuelto();
    return 0;
}

Ejemplo de uso

La clase Laberinto la veremos en breve. Básicamente, se lee el fichero, almacenando el tamaño que tiene y se construye un laberinto de dicho tamaño y cambiando la representación del laberinto, es decir Laberinto lab('+',' ','#',FIL,COL); crea un laberinto de tamaño FILxCOL, cuya representación será un # para el camino que conduce a la salida, + para las paredes y un espacio en blanco para las celdas libres. La siguiente línea imprime el laberinto sin resolver, quedando así:

./bin/laberinto < labs/lab_peque.txt
+++++++
+e    +
+ + +++
+ +   +
+ + +++
+    s+
+++++++

Las dos siguientes líneas resuelven e imprimen el laberinto con el camino hacia la salida:

LABERINTO RESUELTO:
+++++++
+e##  +
+ +#+++
+ +#  +
+ +#+++
+  ##s+
+++++++

En caso de que el laberinto no tenga solución se informa de ello:

./bin/laberinto < labs/lab_sinsolucion.txt
+++++++
+e  +s+
+++++++
El laberinto no tiene salida

Clase Laberinto

La definición del Laberinto es la siguiente:

#include </vector><vector>

class Laberinto{

private:
    std::vector<std::vector><int> > path;
    std::vector</int></std::vector><std::vector><char> > laberinto;
    char shapeP,
         shapeL,
         shapeC;

    void addPathToLab(unsigned int,unsigned int);
    std::vector<int> findEnter() const;
    void cargarLaberinto(unsigned int,unsigned int);

public:
    Laberinto(char p, char l, char c, int x, int y){
        setShapeC(c);
        setShapeP(p);
        setShapeL(l);
        cargarLaberinto(x,y);
    }

    void resolverLaberinto();
    void printLab() const;
    void printLabResuelto() const;

    //Getters y setters
    void setShapeP(char p)    { (*this).shapeP = p; }
    void setShapeL(char l)    { (*this).shapeL = l; }
    void setShapeC(char c)    { (*this).shapeC = c; }

    char getShapeP() const    { return (*this).shapeP; }
    char getShapeL() const    { return (*this).shapeL; }
    char getShapeC() const    { return (*this).shapeC; }
};

En path se almacena el camino recorrido hasta el momento. Internamente, se crea una matriz de igual tamaño que el laberinto, pero booleana que irá llevando la cuenta de los lugares por los que ha pasado.

La implementación:

#include </int></char></std::vector></vector></iostream><iostream>

#include "Laberinto.h"

using namespace std;

void Laberinto::cargarLaberinto(unsigned int FIL,unsigned int COL){
    (*this).laberinto.assign(FIL,vector<char>(COL));
        for(unsigned int i=0; i < FIL; i++)
            for(unsigned int j=0; j < COL; j++){
                char car;
                cin >> car;
                if (car != 'e' && car != 's')
                   (*this).laberinto[i][j] = (car == 'p' ? getShapeP() : getShapeL());
                else
                    (*this).laberinto[i][j] = car;
            }
}

void Laberinto::printLab() const{
    for(unsigned int i=0; i < (*this).laberinto.size(); i++){
        for(unsigned int j=0; j < (*this).laberinto[i].size(); j++)
            cout << (*this).laberinto[i][j];
        cout << endl;
    }
}

void Laberinto::printLabResuelto() const{
    if(!(*this).path.empty()){
        //Añadir el camino al laberinto
        cout << "LABERINTO RESUELTO: "<< endl;
        printLab();
    }
    else
        cout << "El laberinto no tiene salida" << endl;
}


void Laberinto::resolverLaberinto(){

    vector<vector><bool> > recorrido((*this).laberinto.size(), vector</bool><bool>((*this).laberinto[0].size(),false));


    (*this).path.push_back(findEnter());
    recorrido[path[0][0]][path[0][1]] = true;

    vector<int> ultimoPath;
    while(!(*this).path.empty() &&
          (*this).laberinto[(*this).path[(*this).path.size()-1][0]][(*this).path[(*this).path.size()-1][1]] != 's'){
        ultimoPath.clear();
        ultimoPath.push_back((*this).path[(*this).path.size()-1][0]);
        ultimoPath.push_back((*this).path[(*this).path.size()-1][1]);

        //Elemento a la izquierda de la ultima posicion de (*this).path
        if(((*this).laberinto[ultimoPath[0]][ultimoPath[1]-1] != getShapeP())
           && (!recorrido[ultimoPath[0]][ultimoPath[1]-1])){
            ultimoPath[1] = ultimoPath[1]-1;
            (*this).path.push_back(ultimoPath);
            recorrido[ultimoPath[0]][ultimoPath[1]] = true;
        }
        //Elemento a la derecha
        else if ((*this).laberinto[ultimoPath[0]][ultimoPath[1]+1] != getShapeP()
           && !recorrido[ultimoPath[0]][ultimoPath[1]+1]){
            ultimoPath[1] = ultimoPath[1]+1;
            (*this).path.push_back(ultimoPath);
            recorrido[ultimoPath[0]][ultimoPath[1]] = true;
        }
        //Elemento de arriba
        else if ((*this).laberinto[ultimoPath[0]-1][ultimoPath[1]] != getShapeP()
           && !recorrido[ultimoPath[0]-1][ultimoPath[1]]){
            ultimoPath[0] = ultimoPath[0]-1;
            (*this).path.push_back(ultimoPath);
            recorrido[ultimoPath[0]][ultimoPath[1]] = true;
        }//Elemento de abajo
        else if ((*this).laberinto[ultimoPath[0]+1][ultimoPath[1]] != getShapeP()
           && !recorrido[ultimoPath[0]+1][ultimoPath[1]]){
            ultimoPath[0] = ultimoPath[0]+1;
            (*this).path.push_back(ultimoPath);
            recorrido[ultimoPath[0]][ultimoPath[1]] = true;
        }else
            (*this).path.pop_back();
    }

    if(!(*this).path.empty()){
        //Añadir el camino al laberinto
        for(unsigned int i=0; i < (*this).laberinto.size(); i++)
            for(unsigned int j=0; j < (*this).laberinto[i].size(); j++)
                addPathToLab(i,j);
    }
}

vector</int><int> Laberinto::findEnter() const{
    //Buscamos la entrada
    bool encontrada = false;
    vector</int><int> pos;
    for(unsigned int i=0; i < (*this).laberinto.size() && !encontrada; i++)
        for(unsigned int j=0; j < (*this).laberinto[i].size() && !encontrada; j++)
            if((*this).laberinto[i][j] == 'e'){
                pos.push_back(i);
                pos.push_back(j);
                encontrada = true;
            }
    return pos;
}

void Laberinto::addPathToLab(unsigned int i, unsigned int j){
    for (unsigned int k=0; k < (*this).path.size(); k++)
        if((*this).path[k][0] == i && (*this).path[k][1] == j
           && (*this).laberinto[i][j] != 'e' && (*this).laberinto[i][j] != 's')
            (*this).laberinto[i][j] = getShapeC();
}

Más ejemplos

./bin/laberinto < labs/laberinto1.txt
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+e  +     +       +               +     +               +             +   +   + +
+ +++ + +++ +++ +++ +++++++++++ +++ +++ + +++ +++++++++ + +++++ +++++ + + + + + +
+     + +     + +   + +       +       + + +   +     +   + +     +   + + +   +   +
+++++++ + +++++ + +++ + +++++ +++++++++ + + +++ +++ +++ +++ +++++ + + + +++++++ +
+       + + +   +   + + +   + +         + +   + + +   +   +       + +   + +     +
+ +++++++ + + +++++ + + +++ + + +++++++ + +++ + + +++ +++ +++++++++ +++++ + +++++
+       + + +       + +   +     + +     + + +       + + +   +   +   +     + +   +
+ +++++ + + +++++++++ +++ +++++++ + +++++ + +++++++++ + +++ + + + +++ + + + + + +
+     + + +         +   +   + +   + +   + +     +   + +   +   + +   + + + + + + +
+++++ + + + +++ +++ +++ +++ + + + + +++ + + + +++ + + + +++++++ +++ + + +++ +++ +
+ +   +   + + + +       +   + + + +     + + +   + +   + +   +   +   + +   +     +
+ + +++++++ + + +++++++++ +++ + + +++++ + +++++ + +++++ + + + +++ +++ +++ +++++ +
+ + +         + +         +     +     + +     + +   + +   +   +   + +   +       +
+ + + +++++++++ + +++++++ +++++++ + +++ +++++ + +++ + + +++++++++ + +++ +++++++++
+ + +   +   +   + +       +     + +       +   +   + + +   +       +     +     + +
+ + +++++ + + + + +++++++++ +++ +++++++++ + +++ +++ + +++ +++ +++++ +++++ +++ + +
+   +     + + + +         +   + +       + +   +   + +         +   +     +   + + +
+ +++ +++++ + + +++++++++ +++ + + +++++ +++++ +++ + +++++++++++ + +++++ +++ + + +
+     +       +         +     +       +           +         +   +           +  s+
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
LABERINTO RESUELTO:
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+e  +###  +#####  +#############  +#####+###############+      #######+###+###+ +
+#+++#+#+++#+++#+++#+++++++++++#+++#+++#+#+++ +++++++++#+ +++++#+++++#+#+#+#+#+ +
+#####+#+###  +#+###+ +#######+#####  +#+#+   +     +  #+ +#####+###+#+#+###+###+
+++++++#+#+++++#+#+++ +#+++++#+++++++++#+#+ +++ +++ +++#+++#+++++#+#+#+#+++++++#+
+#######+#+ +###+###+ +#+   +#+#########+#+   + + +   +###+#######+#+###+ +#####+
+#+++++++#+ +#+++++#+ +#+++ +#+#+++++++ +#+++ + + +++ +++#+++++++++#+++++ +#+++++
+#######+#+ +#######+ +###+  ###+ +     +#+ +       + + +###+###+###+###  +#+   +
+ +++++#+#+ +++++++++ +++#+++++++ + +++++#+ +++++++++ + +++#+#+#+#+++#+#+ +#+ + +
+     +#+#+         +   +###+ +   + +   +#+     +   + +   +###+#+###+#+#+ +#+ + +
+++++ +#+#+ +++ +++ +++ +++#+ + + + +++ +#+ + +++ + + + +++++++#+++#+#+#+++#+++ +
+ +   +###+ + + +       +###+ + + +     +#+ +   + +   + +###+###+###+#+###+#####+
+ + +++++++ + + +++++++++#+++ + + +++++ +#+++++ + +++++ +#+#+#+++#+++#+++#+++++#+
+ + +         + +#########+     +     + +#####+ +   + +###+###+  #+ +###+#######+
+ + + +++++++++ +#+++++++ +++++++ + +++ +++++#+ +++ + +#+++++++++#+ +++#+++++++++
+ + +   +   +   +#+       +#####+ +       +###+   + + +###+  #####+#####+#####+ +
+ + +++++ + + + +#+++++++++#+++#+++++++++ +#+++ +++ + +++#+++#+++++#+++++#+++#+ +
+   +     + + + +#########+###+#+#######+ +###+   + +    #####+   +#####+###+#+ +
+ +++ +++++ + + +++++++++#+++#+#+#+++++#+++++#+++ + +++++++++++ + +++++#+++#+#+ +
+     +       +         +#####+###    +#######    +         +   +      #####+##s+
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


./bin/laberinto < labs/laberinto2.txt
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+e    +                     +       +   +           +           +             +     +               +
+ +++ +++++ +++++ +++++++++ + +++++ + + + +++ +++++++ + + +++++ +++++++ +++++++ +++ + +++++ +++++++ +
+   + +   +   +   +     +   +     + + +   + +         + + +   +   +     +       +   + +     +     + +
+++ + + + +++++ +++ +++ + +++++++++ + +++++ +++++++++++ +++ + +++ + +++ + +++++++ +++ + +++++ +++ + +
+   +   + +   +     + + +           + +           +     +   +   +   +   + +   + + + + +     +   + + +
+ +++++++ + + +++ +++ + +++++++++++ + + +++ +++++ + +++++ +++++ +++++ +++ + + + + + + +++++ +++ + + +
+     +   + +   + +   +           + + + +   +   + +       +     +   +   +   + + + +     +   +   + + +
+ +++ + +++ +++ + +++ +++++++ +++ +++ +++ +++ + +++++++++++ +++++ +++++ +++++ + + +++++++ +++ +++ + +
+ + + + +   + + +     + +   +   +   +   + +   +         + +   +       + +     + +     +   + +   + + +
+ + + + +++ + + +++++ + + + +++ +++ +++ + + +++++++ +++ + +++ +++++++ + + +++++ +++++ + +++ + + +++ +
+ + + + +   + +   +     + +   + +     + +   +   +   + +   + +   +     + + + +       +   +   + +     +
+ + + + + +++ +++ + +++++ +++ +++ +++ + +++++ + + +++ +++ + +++ + +++++ + + + +++++ +++++ + + +++++++
+ + + + +   +     + +   + +   +   +   +       + + +           + +   +   + +       +       + + +   + +
+ + + + +++ + +++++ + + + +++ + +++ +++++++++++ + +++++++++++++ + + + +++ +++++++++ +++++++ + + + + +
+   + +     +     + + + +   + +   +       +     + +   +         + + + + +         + +   +   +   +   +
+++ + +++++++++++ +++ + + + + + + +++++++++ +++++ + + + + +++++++++ + + +++++++++ + + + + + +++++++ +
+   + +   +           + + + + + +         +   +   + +   + + + +     + +         + + + +   + + +     +
+++++ + + + +++++++++++ +++ + +++++++++ + +++ + +++ +++++ + + + + +++ + +++ +++++ +++ +++++ + + +++++
+     + +   + +     + +     +   +     + +   + +   + +     + +   +     + +   +     +   +   + + +   + +
+ +++++ +++++ + +++ + +++++++++ + +++ +++++ + +++ + + +++++ +++++++ +++++ +++ +++++ +++ + + + +++ + +
+   +   +     +   + +       +     +       +       + + +   +       +       +   +     +   + +   +   + +
+ + + +++ +++ +++ + + +++ +++ +++++++++++ +++++++ + + + +++++++++ +++ +++++ +++++++ + + +++++ + +++ +
+ + +   + +   +   + +   + +   + +     +   +     + + +   +       +   + +     +   +   + +     + +   + +
+ + +++ +++ +++ +++ + + +++ +++ + +++ +++ + +++ +++ + +++ +++++ +++ +++ +++++ + + +++ +++++ + +++ + +
+ +   +     +   + + + +     +   + + +   +   +       + +   +   +   +     +     +   +       +     + + +
+ +++ +++++++ +++ + +++++++ +++ + + +++ +++++++++++++ + +++ +++ +++++++++++++ +++++ +++++++ +++++ + +
+   + +     + +   + +     +     + +   +   +         + + +     +     +         +   +   +   + +   + + +
+++ + + +++ + + + + + +++ +++++++ +++ +++ + +++++++ +++ +++++ +++++ + + +++++++ + +++++ + +++ + + + +
+   +     +     + +     +               +         +               +   +         +       +     +    s+
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
LABERINTO RESUELTO:
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+e    +                     +       +   +           +           +             +     +               +
+#+++ +++++ +++++ +++++++++ + +++++ + + + +++ +++++++ + + +++++ +++++++ +++++++ +++ + +++++ +++++++ +
+###+ +   +   +   +     +   +     + + +   + +         + + +   +   +     +       +   + +     +     + +
+++#+ + + +++++ +++ +++ + +++++++++ + +++++ +++++++++++ +++ + +++ + +++ + +++++++ +++ + +++++ +++ + +
+###+   + +   +     + + +           + +           +     +   +   +   +   + +   + + + + +     +   + + +
+#+++++++ + + +++ +++ + +++++++++++ + + +++ +++++ + +++++ +++++ +++++ +++ + + + + + + +++++ +++ + + +
+#####+   + +   + +   +           + + + +   +   + +       +     +   +   +   + + + +     +   +   + + +
+ +++#+ +++ +++ + +++ +++++++ +++ +++ +++ +++ + +++++++++++ +++++ +++++ +++++ + + +++++++ +++ +++ + +
+ + +#+ +   + + +     + +   +   +   +   + +   +         + +   +       + +     + +     +   + +   + + +
+ + +#+ +++ + + +++++ + + + +++ +++ +++ + + +++++++ +++ + +++ +++++++ + + +++++ +++++ + +++ + + +++ +
+ + +#+ +   + +   +     + +   + +     + +   +   +   + +   + +   +     + + + +       +   +   + +     +
+ + +#+ + +++ +++ + +++++ +++ +++ +++ + +++++ + + +++ +++ + +++ + +++++ + + + +++++ +++++ + + +++++++
+ + +#+ +   +     + +   + +   +   +   +       + + +           + +   +   + +       +       + + +   + +
+ + +#+ +++ + +++++ + + + +++ + +++ +++++++++++ + +++++++++++++ + + + +++ +++++++++ +++++++ + + + + +
+   +#+     +     + + + +   + +   +       +     + +   +         + + + + +         + +   +   +   +   +
+++ +#+++++++++++ +++ + + + + + + +++++++++ +++++ + + + + +++++++++ + + +++++++++ + + + + + +++++++ +
+   +#+   +           + + + + + +         +   +   + +   + + + +     + +         + + + +   + + +     +
+++++#+ + + +++++++++++ +++ + +++++++++ + +++ + +++ +++++ + + + + +++ + +++ +++++ +++ +++++ + + +++++
+#####+ +   + +#####+ +     +   +     + +   + +   + +     + +   +     + +   +     +   +   + + +   + +
+#+++++ +++++ +#+++#+ +++++++++ + +++ +++++ + +++ + + +++++ +++++++ +++++ +++ +++++ +++ + + + +++ + +
+###+   +     +###+#+       +     +       +       + + +   +       +       +   +     +   + +   +   + +
+ +#+ +++ +++ +++#+#+ +++ +++ +++++++++++ +++++++ + + + +++++++++ +++ +++++ +++++++ + + +++++ + +++ +
+ +#+   + +   +###+#+   + +   + +#####+   +     + + +   +#######+   + +     +   +   + +     + +   + +
+ +#+++ +++ +++#+++#+ + +++ +++ +#+++#+++ + +++ +++ + +++#+++++#+++ +++ +++++ + + +++ +++++ + +++ + +
+ +###+     +###+ +#+ +     +   +#+ +###+   +       + +###+   +#  +     +     +   +       +     + + +
+ +++#+++++++#+++ +#+++++++ +++ +#+ +++#+++++++++++++ +#+++ +++#+++++++++++++ +++++ +++++++ +++++ + +
+   +#+#####+#+   +#+#####+     +#+   +###+#########+ +#+     +#####+###      +###+   +###+ +###+ + +
+++ +#+#+++#+#+ + +#+#+++#+++++++#+++ +++#+#+++++++#+++#+++++ +++++#+#+#+++++++#+#+++++#+#+++#+#+ + +
+   +###  +###  + +###  +#########      +###      +#####          +###+#########+#######+#####+####s+
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


Referencias

Asignatura fundamentos de la programación de la Universidad de Granada.

Índice

</int></bool></vector></char></iostream>