Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsShortest path algorithms

Lee's algorithm

Bidirectional Propagation

Report a typo

One useful modification of the Lee algorithm is to propagate from start and target points alternately. In this case, the algorithm is finished when two points from different origins are intersected. Sometimes this modification allows the algorithm to find the shortest path faster while also using less additional memory. Your task here is to apply the Lee algorithm with this modification for the following grid:

Bidirectional Propagation

Apply the first iteration of the Lee algorithm for SS, then move to TT, after that return to SS again and so on. Print the coordinates of the first intersection of two points from different origins (SS and TT) as an answer to this problem. For example, it may look like this:

4 2

The first number is the row and the second number is the column.

Enter a short text
___

Create a free account to access the full topic