Finding path in a char array

Question

I am working on a project and I've found myself in a position where I have a n x n char array of signs a,b or c I have to check if there is a path of b's between the first and the last row. Example YES input:

I am stuck at this point? Should I adapt some well-known algorithm for graph searching or is there any better way of solving this problem? Should I add a bool array to mark which cell I have visited? Thanks in advance for your time!

Answer 1

Yes, you should adopt a graph algorithm for finding the path from a source to the target. In your case you have multiple sources (all 'b's in the first row) and multiple targets ('b's in the last row).

Shortest path on an unweighted graph can be solved pretty efficiently by the easily implemented BFS. Only difference to handle multiple sources is to initialize the queue with all the 'b's on the first line (and not a single node).

In your graph every 'b' cell is a node, there is an edge between every two adjacent 'b' cells.

Note that BFS is complete (always finds a solution if one exists) and optimal (finds shortest path).