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 easilyint dc[] = {0, 1, 0, -1};queue
    
      X, Y; // the queues used to get the positions in the matrixX.push(start_x); // initialize the queues with the start positionY.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();      }}
    

翻译自:

lee最短路算法