lee最短路算法

Lee算法是什么？ (What is the Lee Algorithm?)

The Lee algorithm is one possible solution for maze routing problems. It always gives an optimal solution, if one exists, but is slow and requires large memory for dense layout.

Lee算法是迷宮路由問題的一種可能解決方案。 如果存在的話，它總是提供最佳的解決方案，但是速度很慢，并且需要較大的內存才能進行密集的布局。

了解其運作方式 (Understanding how it works)

The algorithm is a ?breadth-first ?based algorithm that uses ?queues ?to store the steps. It usually uses the following steps:

該算法是基于breadth-first算法，該算法使用queues來存儲步驟。 它通常使用以下步驟：

1. Choose a starting point and add it to the queue.
   選擇一個起點并將其添加到隊列中。
2. Add the valid neighboring cells to the queue.
   將有效的相鄰單元格添加到隊列中。
3. Remove the position you are on from the queue and continue to the next element.
   從隊列中刪除您所在的位置，然后繼續下一個元素。
4. Repeat steps 2 and 3 until the queue is empty.
   重復步驟2和3，直到隊列為空。

實作 (Implementation)

C++ has the queue already implemented in the ?<queue> ?library, but if you are using something else you are welcome to implement your own version of queue.

C ++在<queue>庫中已經實現了<queue> ，但是如果您使用其他方法，則歡迎實現自己的隊列版本。

C ++代碼： (C++ code:)

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<int> X, Y; // the queues used to get the positions in the matrixX.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 positiony = Y.front();for(int i = 0; i < 4; i++){xx = x + dl[i]; // travel in an adiacent cell from the current positionyy = 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 queueY.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 itY.pop();    }
}

翻譯自: https://www.freecodecamp.org/news/lee-algorithm-maze-explained/

lee最短路算法