I was asked a question, given a matrix where each cell can either have a lion sleeping or an empty string, a starting point and an ending point, return the minimum distance you will encounter from lions while taking a path from starting to ending point. You should take a path which maximizes this distance. There could be more than one lion in the grid. Distance is manhattan distance.

How to solve this ?

Edit: We can move in four directions (up, down, left, right). If not path exist, we can also step on lion cell