bueno pues el algoritmo que pretendes es bastante chungo, pero voy a darte alguana idea:
lo que puedes hacer para crear el laberinto es poner toda la matriz como pared e ir "escabando" es decir creando una solución al laberinto, posteriormente puedes realizar más "escabaciones" aleatorias sin preocuparte de que produzcan o no solucion.
¿sabes que es un grafo?
yo para hacer esto utilizaría un grafo, pero si no sabes que es un grafo o no puedes utilizarlo o no sabes implementarlo lo tienes chungo tio.
si sabes lo que es puedes utilizarlo para obtener un mayor nivel de abstracción,
puedes crear un grafo con nodos que sean posiciones en la matriz y unirlos por caminos
algo así
#define N 20
#define M 20 // dimensiones de la matriz
//tipo vertice
typedef struct vertice{
int identificador;
int x; //posicion x del vertice en la matriz
int y; //posicion y del vertice en la matriz
}
Grafo g;
g.crear(); // creacion del grafo
vertice v;
vertice siguiente;
v.x = 0;
v.y = 0;
for ( int i = 0 ; i<10;i++){
siguiente.x = random(N);
siguiente.y = random(Y);
g.insertar_arco(v,siguiente);
v = siguiente;
}
siguiente.x = N
siguiente.y = M
g.insertar_arco(v, siguiente);
// esto lo que hace es insertar un camino complejo de 11 vertices desde la posicion 0,0 hasta la posicion N,M que es la solucion del laberinto.
ahora te hace falta una función que "escabe" desde el origen de un camo hasta el destino algo así:
void escabar_camino(vertice n_origen, vertice n_destino, matriz &m){
// n_origen es un vertice del grafo
// n_destino es otro vertice del graf
// precondicion: existe un camino desde n_origen a n_destino
int j = n_origen.y;
if (n_destino.x < n_origen.x){
for( int i = n_origen.x; i < n_destino. x; i++)
matriz[i][j] = 0; //dejamos libre esa posicioin de la matriz
}
else{
for( int i = n_origen.x; i > n_destino. x; i++)
matriz[i][j] = 0; //dejamos libre esa posicioin de la matriz
}
// escabamos horizontalmente
if (n_origen.y < n_destino.y){
for( j = n_origen.y ; j < n_destiino.y; j++){
matriz[i][j] = 0; // dejamos libre esa posicion de la matriz
else{
for( j = n_origen.y ; j < n_destiino.y; j++){
matriz[i][j] = 0; // dejamos libre esa posicion de la matriz
}
// escabamos verticalmente
//esto crea un camino desde la posicion n_origen hasta la posicion /
//n_destino;
y necesitas una funcion que te cree la solucion del laberinto, para ello tienes que ir sacando los arcos del grafo e ir escabando los caminos con la funcion anterior
void crear_solucion(Grafo G, matriz &m){
Conjunto_arcos arc;
arco a;
vertice orig;
vertice dest;
arc = G.obtener_arcos();
while (!arc.vacio(){
a = arc.elegir();
arc.borrar(a);
orig = g.obtener_vertice(a.origen);
dest = g.obtener_vertice(a.destino);
escabar_camino(ori, dest, M);
}
}
si tienes un tad conjunto y un tad grafo ya lo tienes todo echo.
y ya tienes la solucion del laberinto creada.
ahora lo que puedes hacer es insertar vertices aleatorios en el grafo
y arcos aleatorios también
y llamar a la funcion escabar camiinos y ya tendrias el laberinto creado.
para encontrar la solucion al algoritmo busca por internet
BACKTRACKING
es un esquema algoritmico que te puede ayudar mucho a realizar el algoritmo que resuelva el laberinto.
pero lo que pretendes es muy muy complicado
si no encuentras nada sobre backtracking
visita http://quercusseg.unex.es/agomez/eda.htm y bajte el tema 10 que hay vas a encontrar el backtracking
espero haberte servido de ayuda, aunque no sepas implementar un grafo mira por internet lo que es y coge ideas, lo principal es tener en mente como resolver el problema, despues la implementacion es lo de menos, lo importante es el concepto.
