Solucionador de laberintos en C++
El algoritmo de resolución de laberintos es un problema clásico en informática e inteligencia artificial.
Solucionador de laberintos en C++
El algoritmo de resolución de laberintos tiene como objetivo encontrar el camino más corto de principio a fin moviéndose solo en las cuatro direcciones de la brújula. El algoritmo mantiene dos conjuntos de información: la lista abierta, que contiene todos los nodos que aún no se han visitado, y la lista cerrada, que contiene todos los nodos que se han visitado.
Para encontrar una ruta de un nodo a otro nodo en el laberinto, debemos hacer lo siguiente:
-
Compruebe si un nodo abierto es adyacente (izquierda o derecha) al nodo actual.
-
De lo contrario, verifique si un nodo cerrado es adyacente (izquierda o derecha) al nodo actual.
-
De lo contrario, retroceda un paso y vuelva a realizar los pasos 1 y 2.
Ejemplo del algoritmo de resolución de laberintos:
#include <iostream>
using namespace std;
bool demo_maze(char maze[9][9], bool sam[9][9], int x, int y, int u, int v) {
if (x == u && y == v) {
sam[x][y] = true;
for (int t = 0; t <= u; t++) {
for (int f = 0; f <= v; f++) {
cout << sam[t][f] << " ";
}
cout << endl;
}
cout << endl;
return true;
}
if (x > u || y > v) return false;
if (maze[x][y] == 'X') return false;
sam[x][y] = true;
bool right = demo_maze(maze, sam, x, y + 1, u, v);
bool down = demo_maze(maze, sam, x + 1, y, u, v);
sam[x][y] = false;
if (right || down) return true;
return false;
}
int main() {
char maze[9][9] = {"0000", "00X0", "000X", "0X00"};
bool sam[9][9] = {0};
int u = 3, v = 3;
bool ans = demo_maze(maze, sam, 0, 0, u, v);
}
Haga clic aquí para verificar el funcionamiento del código como se mencionó anteriormente.
Usos del Maze Solver en C++
El algoritmo de resolución de laberintos se puede utilizar para muchos propósitos, incluidos el ajedrez, el buscaminas y la búsqueda de caminos a través de laberintos u otros obstáculos en un mapa. ¡Este algoritmo puede decidir qué camino tomar cuando te pierdes y buscas la salida de un bosque o laberinto!
El algoritmo de resolución de laberintos también se usa para juegos 2D, pero llevaría más tiempo que otros algoritmos debido a su complejidad computacional. Utiliza una función recursiva que verifica las coordenadas del jugador y luego lo mueve al siguiente lugar.
Una función recursiva se llama a sí misma, ya sea directa o indirectamente. Se puede usar para resolver problemas de recursividad y también se puede usar para resolver problemas en los que la solución no se expresa fácilmente como un bucle corto.
Muhammad Adil is a seasoned programmer and writer who has experience in various fields. He has been programming for over 5 years and have always loved the thrill of solving complex problems. He has skilled in PHP, Python, C++, Java, JavaScript, Ruby on Rails, AngularJS, ReactJS, HTML5 and CSS3. He enjoys putting his experience and knowledge into words.
Facebook