problem with breadth first search

how do i implement breadth first search using a queue to find the shortest path from the upper left corner to the lower right corner, if there is one.A path can only go up, down, or sideways (not diagonally) and must only pass through zeros. The ones are walls. The number of rows will not exceed 40, and the number of columns will not exceed 78. if im not being clear this is an example.

input:
3 5
01000
00010
01010


output:
01000
00010
01010
( 1, 1)( 2, 1)( 2, 2)( 2, 3)( 1, 3)( 1, 4)( 1, 5)( 2, 5)( 3, 5)

Most graph search algorithms are based on a connection table. It is a bit unclear as to where the vertices and edges are in your example. I think you need to start by abstracting a connection table from your input, after that point is should be easy. cpp has a number of graph library functions, if you are planning on using them, make sure that the format of the connection table you develop is in the same form as the expected input to the std graph functions. That will save you having to create an abstraction to translate.

It also seems as if you would want a depth-first search, or a hybrid. The simple way is to find all paths and then just count to see what the shortest is. Otherwise you need to develop a cost metric for deciding which path to follow when there is more than one choice.

LMHmedchem

http://en.wikipedia.org/wiki/Breadth-first_search

If you tell me the name of the course and year in curriculum, I may give you more. :)