How to apply BFS in such scenario?



There is one grid




where ‘.’ represent visible path, ‘*’ represent check point, ‘@’ represent starting point and ‘x’ represent blocked path.

Now I want to find minimum distance from source to each check point and from each check point to every other check point.

Basically I want to make a weighted complete graph that comprises of all check points and source where weight of each edge is minimum distance between that point to other point.

Refer this problem on spoj for further details.


Your problem is similar to this spoj problem :

You can find it’s solution here :



I have already mentioned the link to the problem.Can you please explain me the logic.