Given a 2D matrix consisting of 'o’s and ‘x’, we need to calculate the shortest path to reach from any x in the first row to any x in the last row. It is possible to travel in all 8 directions. There may be more than one number of x’s in the first and last row. Print -1 if it’s not possible to reach any of the x’s in the last row.
1<row<1000
1<column<1000
eg. o o x
x x o
x o o
O/P- 2
How to approach this problem?
Actually it was a private contest so I cant share the link of the question. Sorry. But I remember the question quite well.
Okay so what ai can think of is its a simple BFS question
Just push all the 1st row elements which have x as i,j,1 in queue
And then keep popping from queu and keep adding unvisited x’s in its neighbor until u reach a x which is having i==n
Complexity will be O(n^2) in terms of both space and time
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
