Se dispone de una matriz de N x M que representa un laberinto compuesto de paredes y baldosas (1 y 0), este laberinto consta de entradas ubicadas en la primera fila y salidas en la última fila.
Se pide:
-Encontrar todos los caminos hacia la salida.
-Almacenar en una lista simplemente encadenada los pasos que se involucran en camino.
-N y M son valores ingresados por el usuario.
-Mostrar matriz y la lista.
Laberinto.cpp(Backtracking)
Código:
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include"Laberinto.h";
#include"Matriz.h";
using namespace std;
bool Solucion = false;
Laberinto::Laberinto(int f,int c){
filas = f
columnas= c
mat = new int*(filas);
for(int contador = 0; contador < columnas;contador++){
mat[contador]= int[columnas];
}
void Laberinto::recorrer(int mat[f][c],int i,int j, int pasos){
if(i-1>=0 && i-1<f &&(laberinto[i-1][j]=='0' ||//Arriba
return true;
recorrer(laberinto,i-1,j,pasos+1);
if(j+1>=0 && j+1<c &&(laberinto[i][j+1]=='0' ||//Derecha
return true;
recorrer(laberinto,i,j+1,pasos+1);
if(i+1>=0 && i+1<f &&(laberinto[i+1][j]==' ' ||//Abajo
recorrer(laberinto,i+1,j,pasos+1);
return true;
if(j-1>=0 && j-1<c &&(laberinto[i][j-1]=='0' ||//Izquierda
recorrer(laberinto,i,j-1,pasos+1);
return true;
if(i-1>=0 && i-1<f && j+1>= && j+1<c(laberinto[i-1][j+1]=='0' ||//ArribaDerecha
recorrer(laberinto,i-1,j+1,pasos+1);
return true;
if(i-1>=0 && i-1<f && j-1>= && j-1<c(laberinto[i-1][j-1]=='0' ||//ArribaIzquierda
recorrer(laberinto,i-1,j-1,pasos+1);
return true;
if(i+1>=0 && i+1<f && j+1>= && j+1<c(laberinto[i+1][j+1]=='0' ||//AbajoDerecha
recorrer(laberinto,i+1,j+1,pasos+1);
return true;
if(i+1>=0 && i+1<f && j-1>= && j-1<c(laberinto[i+1][j-1]=='0' ||//AbajoIzquierda
recorrer(laberinto,i+1,j-1,pasos+1);
return true;
laberinto[i][j] = '0';
return false;
}
Matriz.cpp
Código:
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include "Matriz.h";
using namespace std;
//Main srand(time(NULL));
/*Main cout<<"cantidad filas";
cin>>filas;
cout<<"cantidad columnas";
cin>>columnas;
*/
Matriz::Matriz(int f,int c){
filas = f
columnas= c
mat = new int*(filas);
for(int contador = 0; contador < columnas;contador++){
mat[contador]= int[columnas];
}
llenarMatriz();
}
void Matriz::llenarMatriz{
for (int i = 0; i<filas;i++){
for(int j = 0; j<columnas;j++){
mat[i][j] = return (int) rand()% 2;
}
}
}
void Matriz::mostrarMatriz{
for(int i = 0; i<filas; i++){
for(int j = 0; j<columnas;j++){
cout << mat[j][i];
}
cout << endl;
}
}
Matriz::~Matriz(){
}
Main.cpp
Código:
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include "Matriz.h";
using namespace std;
int main(){
Matriz *m;
int n;
int continuar;
do{
cout<<"------------------------------"<<endl;
cout<<"1.Crear Laberinto nxm" << endl;
cout<<"2.Mostrar Lista" << endl;
cout<<"------------------------------"<<endl;
cin >> n;
switch(n){
case 1: {
int c;
int f;
cout << "Ingrese cantidad de filas" << endl;
cin >> f;
cout << "Ingrese cantidad de columnas" << endl;
cin >> c;
m= new Matriz();
m->mostrarMatriz();
}
//case 2:{
do{
cout<<"Desea Continuar? 1.Si/0.No" << endl;
cin << continuar;
}while(continuar < 0 or continuar > 1);
}while(continuar !=0);
return(0);
}
}