So anybody thinking,how to find all the nodes which might be on the shortest path from (1,1) to (n,m) , here’s what we do, for each node situated at (i,j), if minimum cost to travel from (1,1) to (i,j) + minimum cost to travel from (i,j) to (n,m) - a(i,j)= x , then that node lies on one of the shortest paths from (1,1) to (N,M),where x=shortest path from (1,1) to (N,M)
Now, make a special graph G (unweighted) of all these nodes.
Now, from node (1,1) to node (n,m) all paths of this special graph G have equal length , so you can without any tension, do a special kind of bfs on this graph. And for each level from (1 to k=n+m),find the minimum character node.
If for level-1,minimum character node=‘a’, for level-2, its ‘b’,for level ‘3’,its ‘c’. Then the final answer will be “abc”
Meaning of my special BFS:–>“You are at the root, see all connected guys to it, all guys which have minimum value, only they should be pushed in the queue, keep doing this till you reach node (n,m) .”
Thanks for the valuable inputs! @nishant403