¿Qué es el algoritmo de Lee?
El algoritmo de Lee es una posible solución para los problemas de enrutamiento de laberintos. Siempre ofrece una solución óptima, si existe, pero es lenta y requiere mucha memoria para un diseño denso.
Entendiendo como funciona
El algoritmo es un breadth-first algoritmo basado que se utiliza queues para almacenar los pasos. Suele seguir los siguientes pasos:
- Elija un punto de partida y agréguelo a la cola.
- Agregue las celdas vecinas válidas a la cola.
- Elimine la posición en la que se encuentra de la cola y continúe con el siguiente elemento.
- Repita los pasos 2 y 3 hasta que la cola esté vacía.
Implementación
C ++ ya tiene la cola implementada en la biblioteca, pero si está usando algo más, puede implementar su propia versión de la cola.
Código C ++:
int dl[] = {-1, 0, 1, 0}; // these arrays will help you travel in the 4 directions more easily int dc[] = {0, 1, 0, -1}; queue X, Y; // the queues used to get the positions in the matrix X.push(start_x); // initialize the queues with the start position Y.push(start_y); void lee() { int x, y, xx, yy; while(!X.empty()) // while there are still positions in the queue { x = X.front(); // set the current position y = Y.front(); for(int i = 0; i < 4; i++) { xx = x + dl[i]; // travel in an adiacent cell from the current position yy = y + dc[i]; if('position is valid') //here you should insert whatever conditions should apply for your position (xx, yy) { X.push(xx); // add the position to the queue Y.push(yy); mat[xx][yy] = -1; // you usually mark that you have been to this position in the matrix } } X.pop(); // eliminate the first position, as you have no more use for it Y.pop(); } }