There is a matrix of size (M x N) in which the cells are marked by one of the three letters (either 'a','b' or 'c'). Now given that there is only one cell that is marked with value 'a' but more than one cells can be marked with value 'b' or 'c'.
There is 8 ways in which one can move form one cell to another, considering rowwise, columnwise, diagonal and anti-diagonal movements to the next cell. taking the cell marked by 'a' as starting cell and cells marked by 'c' as destination cells. The length of a route is defined as the total number of steps taken while moving from starting to a destination cell without going through the cells marked by value 'b'.
What is the minimum length of the route for a given matrix with all the cells properly marked with values either 'a','b' or 'c'? I tried using the recursive implementation which basically is taking long time (as it checks all the 8 directions and then it gives the best of them). Can I get a better solution approach may be through DP? Any help is greatly appreciated.