Објашњени Лее алгоритам: трчање лавиринтом и проналажење најкраћег пута

Шта је Лее алгоритам?

Лее алгоритам је једно од могућих решења за проблеме усмеравања лавиринтом. Увек даје оптимално решење ако постоји, али је споро и захтева велику меморију за густи распоред.

Разумевање како то функционише

Алгоритам је   breadth-first  заснован алгоритам који користи   queues  за чување корака. Обично користи следеће кораке:

  1. Изаберите почетну тачку и додајте је у ред.
  2. Додајте важеће суседне ћелије у ред.
  3. Уклоните позицију на којој сте на реду и наставите до следећег елемента.
  4. Понављајте кораке 2 и 3 док се ред не испразни.

Имплементација

Ц ++ има ред већ имплементиран у    библиотеци, али ако користите нешто друго, добродошли сте да примените своју верзију реда.

Ц ++ код:

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(); } }