You are given a matrix of characters and a starting point inside of the matrix. Every entry in the matrix except for one has the letter U, D, L, or R in it. When you are at an index that has an U, you most go up in the matrix. The same applies for the other characters (you must go down, left, or right, respectively).

We can represent this problem as a directed graph in which the entry (i, j) has an edge to one of its four neighbors if the entry at (i, j) tells us to move to that neighbor.

One entry in the matrix is marked “x”. In a single turn, you are allowed to choose an entry (i, j) and change its value to any one of U, D, L, or R. What is the minimum number of operations that you need to perform in order to ensure that one can reach the entry marked “x” from the given starting point? In other words, we can change the direction of any edge at a cost of one.

My initial thought is one can do a DFS from the starting point. If we can already reach x, the answer is zero. However, the problem is more complicated when we need to change edges. I feel that we can just reach any vertex that leads into x, so it’s not enough to just run a BFS from x either. Any help is appreciated.