Is it possible to apply breadth-first search algorithm of boost library to matrix?
-
11-11-2019 - |
Question
My task is to find the shortest way in a matrix from one point to other. It is possible to move only in such direction (UP, DOWN, LEFT, RIGHT).
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 0 1 0 1 F 0
0 1 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 S 0 1 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
S - Start point
F - Destination place (Finish)
0 - free cells (we can move through them)
1 - "walls" (we can't move through them)
It is obvious that a breadth first search solves this problem in the most optimal way. I know that the Boost library supplies this algorithm, but I haven't Boost before.
How can I do a breadth first search in my case using Boost?
As I understood, breadth first search algorithm of Boost is intended only for graphs.
I guess that it isn't a good idea to convert matrix to graph with m*n
vertices and m*(n -1) + (m-1)*n
edges.
Can I apply breadth first search algorithm to matrix (without converting it to a graph), or is it better to implement my own function for breadth first search?
No correct solution