需要移动多少步才能到达目的地？高效注水

我想通过四向移动的次数来计算单元格与目标单元格的距离以到达某处。因此，紧邻目的地的四个单元格的距离为 1，每个单元格的四个基本方向上的单元格的距离为 2，依此类推。最大距离可能约为 16 或 20，并且有些单元格被障碍物占据；距离可以绕过它们，但不能穿过它们。

我想将输出存储到二维数组中，并且我希望能够非常快速地计算更大迷宫地图上任何目的地的“距离图”。

我通过洪水填充的变体成功地做到了这一点，其中我将相邻未填充单元格的增量距离放入优先级队列中（使用 C++ STL）。

我对这个功能很满意，现在想专注于优化代码，因为它对性能非常敏感。

可能会有什么狡猾而快速的方法呢？

我认为你做的一切都是对的。如果您编码正确，则需要O(n)时间和O(n)用于计算洪水填充的内存，其中n是细胞的数量，可以证明不可能做得更好（一般情况下）。填写完成后，您只需返回任何目的地的距离即可O(1)，很容易看出它还可以做得更好。

所以如果你想优化性能，你只能关注代码局部优化。这不会影响渐近复杂度，但可以显着提高实际执行时间。但在没有实际查看源代码的情况下，很难给你任何代码优化的建议。

因此，如果您确实想查看优化的代码，请参阅以下内容（纯 C）：

#include <stdlib.h>

int* BFS()
{
    int N, M; // Assume we have NxM grid.
    int X, Y; // Start position. X, Y are unit based.
    int i, j;
    int movex[4] = {0, 0, 1, -1}; // Move on x dimension.
    int movey[4] = {1, -1, 0, 0}; // Move on y dimension.
    
    // TO DO: Read N, M, X, Y
    
    // To reduce redundant functions calls and memory reallocation 
    // allocate all needed memory once and use a simple arrays.
    int* map = (int*)malloc((N + 2) * (M + 2) * sizeof(int)); 
    int leadDim = M + 2;
    // Our map. We use one dimension array. map[x][y] = map[leadDim * x + y];
    // If (x,y) is occupied then map[leadDim*x + y] = -1;
    // If (x,y) is not visited map[leadDim*x + y] = -2;

    int* queue = (int*)malloc(N * M * sizeof(int));
    int first = 0, last =1; 
    
    // Fill the boarders to simplify the code and reduce conditions
    for (i = 0; i < N+2; ++i)
    {
        map[i * leadDim + 0] = -1;
        map[i * leadDim + M + 1] = -1;
    }
    
    for (j = 0; j < M+2; ++j)
    {
        map[j] = -1;
        map[(N + 1) * leadDim + j] = -1;
    }
    
    // TO DO: Read the map.
    
    queue[first] = (X+1) * leadDim + Y + 1;
    map[(X+1) * leadDim + Y + 1] = 0;
    
    // Very simple optimized process loop.
    while (first < last) 
    {
        int current = queue[first];
        int step = map[current];
    
        for (i = 0; i < 4; ++i)
        {
            int temp = current + movex[i] * leadDim + movey[i];
            if (map[temp] == -2) // only one condition in internal loop.
            {
                map[temp] = step + 1;
                queue[last++] = temp;
            }
        }
    
        ++first;
    }
    
    free(queue);
    
    return map;
}

该代码可能看起来很棘手。当然，它不是面向对象（OOP）的，但如果您想要真正快速的东西，那就是您所需要的。