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

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top