Given a matrix containing initial state of each elements, find minimum number of steps to reach from top left to bottom right?

Conditions:

1. Initial state of any element will be randomly one of North, East, South or West.
2. At every step, we can either not move anywhere or move in the direction of current state of that element (ofcourse we never go out of the matrix)
3. Any step will simulatanously change the state of all elements of the matrix. States change in a clockwise cyclic manner i.e from N -> E -> S -> W. Even if we don't move in a step, the states do change

I tried solving it the BFS way, but interviewer was not fully satisified with the solution. Any better approaches?

Similar problems:

• https://leetcode.com/problems/sliding-puzzle