Thanks @simes for your reply
Can you explain how maintaining direction can help to prune the search.
I feel that visiited/univisted should be enough as in my code, once i have visited a cell, i m never going to push it back to queue as it will never lead me to any new cells.
Considering example of yours , if i visited all the cells in row 6, i mark it visited by setting corresponding entry in vis[] array to a non negative number( this is the distance to reach it). Now whenever i reach any cell of the 6th row, i know that all cells in that row is visited so , we ignore it. However if in a path , i encounter these cells, i wont stop my search but skip that cell
S . .
x x .
F . .
As in this example , taking 0 index here
once S (0,0) is popped from queue, it push and visit (0,1) and (0,2) . Now in next iteration, (0,1) is popped that will only visit (1,2) ( as (0,2) is already visited ). Now when (0,2) is popped , it will find that (1,2) is visited , so it skips it, and proceed to visit (2,2).
So,I still could not find the an application of direction here. Can you give any other example where direction works but visited doesnot work?
Thanks