Я думаю, что вы все сделали правильно.Если вы закодировали его правильно, то для вычисления заливки затрачивается время O (n) и память O (n), где n - количество ячеек, и можно доказать, что это невозможно сделать лучше (в общем случае).И после того, как заполнение завершено, вы просто возвращаете расстояние для любого пункта назначения с помощью O (1), легко увидеть, что это также можно сделать лучше.
Так что, если вы хотите оптимизировать производительность, вы можете сосредоточиться только на CODEМЕСТНАЯ ОПТИМИЗАЦИЯ.Что не повлияет на асимптотику, но может значительно улучшить ваше реальное время выполнения.Но трудно дать вам какой-либо совет по оптимизации кода, не видя исходного кода.
Так что, если вы действительно хотите увидеть оптимизированный код, посмотрите следующее (Pure C):
include
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));
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);
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 * leadDim + Y;
map[X * leadDim + Y] = 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;
}
Код может показаться сложным.И, конечно, это не похоже на ООП (я действительно думаю, что фанаты ООП будут ненавидеть это), но если вы хотите что-то действительно быстрое, это то, что вам нужно.