Cretu Bogdan Cretu Bogdan - 1 month ago 19
Java Question

Get effective road from a point to a point (BFS on matrix)

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.