Cretu Bogdan - 4 months ago 37

Java Question

I have a matrix with 0 and X (0 means you can walk through and X means wall).

I have a start point and an end point.

I used BFS to find the shortest path (length) between start and end. (it works)

But now I need to find the effective road and I don't know how to do it. (I thought I can use an Lee algorithm recursiv).

`Example:`

5 5

SXXXF

0XX00

0XX0X

0000X

XXXXX

Length is 8 and the road is: (1, 1) -> (2, 1) -> (3, 1) ->(4, 2) -> (4, 3) -> (3, 4) -> (2, 4) -> (1, 5).

I have 8 directions.

So, I used BFS to get the length (8) but I don't know how to get the road.

Some ideas or pseudocodes?

Thanks!

Answer

Actually it's pretty simple:
Store the "predecessor" of each node. Be it in another matrix, embedded into the original map, or as `Map`

. Even a tree-structure would work, if it's bidirectional.

Without code, I can't got about showing you a possible solution, but in the end, all you need is a mapping `node -> node from which it was visited`

. E.g. in your example you move from `(1, 1)`

to `(2, 1)`

, so the mapping would be `(2, 1)->(1, 1)`

. This can easily be implemented within the BFS-routine.

Finish running the algorithm, while filling your mapping. Afterwards you start of by searching the predecessor of the finish node, then the predecessor of the predecessor of the finish node, and so on until you're back at the start point.