Cretu Bogdan - 10 months ago 54
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!

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.