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.
This problem looks like a typical application of Dijkstra's algorithm for finding the shortest distance between the starting point and the destination point marked "x". At any cell $$$(u,v)$$$, the cost function for moving to an adjacent point inside the matrix is $$$0$$$ if the move is along the direction letter of this point. Otherwise, the cost of move is $$$1$$$. The minimum distance at any point in the matrix is initialized to $$$+\infty$$$, execpt for the starting point at which the minimum distance is initialized to $$$0$$$.