Buscar programación informática profesional: 1. Resolver el problema del laberinto, que requiere generar una matriz de laberinto y encontrar el camino más corto en el laberinto (código original de estructura de datos)
#include
usando el espacio de nombres std;
class T //Define el tipo de estructura que describe la posición actual en el laberinto
{
public:
int x; //x representa la coordenada de la fila de la posición actual
int y //y representa la coordenada de la columna; de la posición actual
p>int dir; //0: invalid, 1: este, 2: sur, 3: oeste, 4: norte
};
clase LinkNode // Nodo de lista enlazada
{
Pila de clases amigas;
público:
Datos T;
LinkNode *siguiente ;
};
clase Pila
{
privado:
LinkNode *top; //Apunta al puntero superior de la pila del primer nodo
public:
Stack() //Constructor, vacía la pila
~Stack(); / /Destructor
void Push(T e); //Empuja los datos del elemento en la pila
T Pop(); elemento superior de la pila
T GetPop(); //Eliminar el elemento superior de la pila
void Clear() //Vaciar la pila
bool vacío(); //Determina si la pila está vacía, si está vacía, devuelve 1, de lo contrario devuelve 0
};
Stack::Stack() //Constructor , vacía la pila
{
top=NULL;
}
Stack::~Stack() //Destructor
{
}
void Stack::Push(T e) //Empuja el elemento x en la pila
{
LinkNode *P;
p>P=nuevo LinkNode;
P->data=e;
P->siguiente=top;
top=P;
}
T Stack::Pop() //Extrae el elemento superior de la pila
{
T Temp;
LinkNode *P;
P=top;
top=top->siguiente;
Temp=P->datos;
eliminar P;
devolver Temp;
}
T Stack::GetPop( ) //Elimina el elemento superior de la pila
{
return top->data;
}
void Stack:: Clear() //Borrar la pila
{
top=NULL;
}
bool Pila:
:empty() //Determina si la pila está vacía. Si está vacía, devuelve 1; de lo contrario, devuelve 0
{
if(top==NULL) devuelve 1;
else devuelve 0;
}
int move[4][2]={{0,1},{1,0},{0, -1 },{-1,0}}; //Definir las 4 direcciones del movimiento de la posición actual
bool Mazepath(int **maze,int m,int n
//Devuelve verdadero si llega, de lo contrario devuelve falso
void PrintPath(Stack p); // Genera la ruta del laberinto
void Restore(int **maze,int m,int n); //Restaura el laberinto
int** GetMaze( int &m,int &n) ; //Obtener el laberinto
//Devolver el puntero bidimensional para acceder al laberinto
int main()
{
int m =0,n=0; //Definir el largo y ancho del laberinto
int **laberinto; //Definir el laberinto de acceso al puntero bidimensional
p>maze=GetMaze(m,n ); //Llama a la función GetMaze(int &m,int &n) para obtener el laberinto
if(Mazepath(maze,m,n)) / /Llame a la función Mazepath(int **maze,int m,int n ) para obtener la ruta
cout<<"¡La ruta del laberinto fue explorada exitosamente!\n";
else cout<<"¡La ruta no existe!\n";
return 0;
}
int** GetMaze(int &m,int &n) // Devuelve el puntero bidimensional para acceder al laberinto
{
int **laberinto; //Definir el acceso al puntero bidimensional
int i =0,j=0;
cout<<"Por favor, ingresa el largo y ancho del laberinto:";
int a,b;cin>>a>>b; Ingrese el largo y ancho del laberinto
cout<<"Ingrese el contenido del laberinto: \n";
m=a;
n =b; //m,n representa el número de filas y columnas del laberinto respectivamente
maze=new int *[m+2] //Solicita un puntero bidimensional con una longitud igual; al número de líneas más 2
for(i= 0;i { laberinto[i]=new int[n+2]; } for(i=1 ;i<=m;i++) //Ingrese el contenido de el laberinto, 0 significa transitable, 1 significa intransitable for(j=1;j<=n;j++) cin>>laberinto[i][j]; for(i=0;i laberinto[i][0]=laberinto[i ][n+1]=1; for(i=0;i laberinto[0] [i]=maze[m+1][i]=1; return maze; //Devuelve el laberinto de puntero bidimensional para almacenar el laberinto }; bool Mazepath(int **maze,int m,int n)//Encuentra el camino de (0, 0) a (m, n) en el laberinto laberinto //Regresar verdadero si se alcanza; de lo contrario, devuelve falso { Pila q,p; //Defina la pila p y q para almacenar el proceso y la ruta de almacenamiento para explorar el laberinto respectivamente T Temp1 ,Temp2; int x,y,bucle; Temp1.x=1; Temp1.y=1; q.Push(Temp1); //Empuja la posición de entrada a la pila p.Push(Temp1); maze[1][1]= -1; // Marcar la entrada La posición ha sido alcanzada while(!q.empty()) // La pila q no está vacía, luego explorar repetidamente { Temp2=q.GetPop (); //Obtener el elemento superior de la pila if(!(p.GetPop().x==q.GetPop().x&&p. GetPop().y==q.GetPop(). y)) p.Push(Temp2 //Si se inserta una nueva posición en la pila, se almacena la última posición explorada en la pila p for(loop=0;loop<4;loop++) //Explora 4 posiciones adyacentes de la posición actual { x=Temp2.x+move[loop][ 0]; //Calcula el nuevo valor de posición x y=Temp2.y+move[loop][1] //Calcula el nueva posición y valor de posición if (maze[x][y]==0) //Determina si la nueva posición es alcanzable { Temp1 .x=x; Temp1. y=y; maze[x][y]=-1; //Marca que se ha alcanzado la nueva posición q.Push(Temp1); //Empuja la nueva posición a la pila } if((x==(m))&&(y==( n))) //Llegué exitosamente a la salida { Temp1.x=m; Temp1.y=n; Temp1.dir=0; p.Push(Temp1) ; //Empuja la última posición en la pila PrintPath(p); //Ruta de salida Restore(maze,m,n); //Restaurar ruta return 1; //Indica que la ruta se encontró correctamente } } if(p.GetPop().x==q.GetPop() .x&&p.GetPop().y==q.GetPop().y) / /Si no se inserta ninguna nueva posición en la pila, regresa a la posición anterior { p.Pop(); q.Pop(); }< /p> } return 0; //Indica que la búsqueda falló, es decir, el laberinto no tiene ruta } void PrintPath (Pila p) / /Ruta de salida { cout<<"El camino del laberinto es\n"; cout<<"El contenido entre paréntesis se expresan como (coordenadas de línea, coordenadas de columna, dirección digital, dirección)\n"; Pila t; //Definir una pila según la ruta de acceso desde la entrada hasta la salida int a,b; T datos; LinkNode *temp; temp=new LinkNode //Solicitar espacio temp->data=p .Pop(); //Obtiene el elemento de vértice de la pila p, es decir, la primera posición t.Push(temp->data); la primera posición se empuja a la pila t delete temp; //Liberar espacio while(!p.empty()) //Si la pila p no está vacía, transfiera repetidamente { temp=new LinkNode; temp->data=p.Pop() //Obtener la siguiente posición //Obtener la dirección para caminar a= t.GetPop().x-temp->data.x; //Dirección de las coordenadas de la fila b=t.GetPop(). y-temp->data.y; // Dirección de las coordenadas de la columna if(a==1) temp->data.dir=1 //La dirección es hacia abajo, representada por 1 else if(b==1) temp->data .dir=2; //La dirección es hacia la derecha, representada por 2 else if(a==-1) temp ->data.dir=3; //La dirección es hacia arriba, representada por 3 else if(b==-1) temp->data.dir=4; izquierda, representada por 4 t.Push(temp->data); // Empuja la nueva posición en la pila delete temp; } //Ruta de salida, incluidas las coordenadas de fila, las coordenadas de columna y la dirección de la siguiente posición while(!t.empty()) //La pila no está vacía, continúa la salida { data=t.Pop(); cout<<'('< switch(data.dir) //Muestra la dirección correspondiente { caso 1:cout<<"↓)\n";break; caso 2:cout<<"→)\n";break; caso 3:cout<<" ↑)\n";break; caso 4:cout< <"←)\n";break; caso 0:cout<< ")\n";break; } } } void Restore(int **laberinto,int m, int n) //Restaurar el laberinto { int i,j; for(i=0;i for(j=0;j { if(laberinto[i][j]==-1 ) //Restaurar la posición explorada, es decir, restaurar -1 a 0 maze[i][j]=0; } } Resultado de ejemplo: Prueba 1: Ingrese el largo y el ancho del laberinto: 5 5 Ingrese el contenido de el laberinto: 0 1 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 El camino del laberinto es El contenido entre paréntesis se expresa como (coordenadas de fila, coordenadas de columna, dirección digital, dirección) ( 1,1,1,↓) (2,1,2,→) (2,2,1,↓) (3, 2,1,↓) (4,2,2,→) (4,3,1,↓) (5,3, 2,→) (5,4,2,→) (5,5,0,) ¡La exploración del camino del laberinto fue exitosa! Prueba 2: Ingrese el largo y ancho del laberinto: 9 8 Ingrese el contenido de el laberinto: 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 El camino del laberinto es El contenido entre paréntesis se expresa como (coordenadas de fila, coordenadas de columna, dirección de digitalización, dirección) (1,1,1,↓) (2,1,1,↓) (3, 1,1,↓) (4,1,1,↓) ( 5,1,2,→) (5,2, 2,→) (5,3,1,↓) (6, 3,2,→) (6,4,2, →) (6,5,3, ↑) (5,5, 2,→) (5,6,2,→) (5,7,1,↓) (6,7,1, ↓) (7,7,1,↓) (8,7,1,↓) (9,7,2, →) (9,8,0,) ¡El camino del laberinto fue explorado con éxito!