# Programming question for a new approach

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.

Construct a graph in which the vertices are all cells not marked 'b', and in which two vertices are connected if they are adjacent in the matrix. Use BFS from the 'a' vertex to go over all vertices in order of distance from 'a', until you find the first 'c' vertex. The overall complexity is $O(MN)$.