Here, I shall explain my original way of solving that problem. I shall use the analogy that the more positive a sensor reads, the happier or more satisfied it is. "Unsatisfied" means that it is below 0.

Basically, we must find the path so that all the sensors (arranged in a square) are barely satisfied. Why barely? The question asks for the lexical ordering - which means that if possible, the R must always come before the U. So we must always move right if possible, as long as the sensors are barely satisfied. If all the sensors are too satisfied and there's still room to move right, we must do so to get the lexically optimal solution.

Firstly, we must realize that we only need to consider the four sensors on the corners. This is because the closer we get to the sensor, the happier it is. A sensor only gets triggered if you spend a lot of time far from it. It is clear that for any path, the furthest sensor to the path must be one of the corner ones. So as long as all four corner sensors are satisfied, the remaining sensors in between must definitely be satisfied. Proof shall be left as an exercise to the reader (okay, just kidding - I quite dislike math textbooks that say that).

Secondly, we must have a good way of representing the path. One obvious way is simply a string of length 2n-2, storing Us and Rs. But as it turns out, it is quite difficult (for me) to work out things using this representation. My way of representing the path is an array of length n that stores the maximum height of the path at each x position. For example, RURURRUU would be {0,1,2,2,4}. Do note that the last element of this array is always n-1, but the first element is not always 0. In my code, I call this array y. The entries of this array must always have the property that y[k]>=y[k-1], that is, it is never decreasing (since Ciel can't walk downwards).

My algorithm to solve the problem is:

1) Initialize the path so that it is RRRRR...RRRRRUUUUU...UUUUU. In other words, y[k]=0 for all k except y[n-1], which is y[n-1]=n-1. 

2) Move the Rs backwards one by one until all sensors are satisfied.

But moving an R backward is the same as incrementing y[k] at that spot! So, for each sensor, we iterate the array y from right to left and increment it if appropriate. We can, of course, increment y[k] by adding one each time but that is too slow. Instead, I calculate a value dy that is the amount to be incremented. First, realize that it only makes sense to increment y[k] if it makes the sensor happier. This means that we should only increment it until the height of the sensor so you might think that dy is simply the height difference between y[k] and the sensor height. But then, also, we only want to increment this until the sensor is just barely satisfied. Hence, dy is simply the minimum of the aforementioned height difference and the 2 times the negative amount in the sensor. Why 2 times? This brings us to the next section:

When changing the path by raising part of it, we must update all the sensors. To think about how to do this, realize that when you change an "RU" segment into a "UR" one, the vertex in the bottom right moves to the top left. To analyze the impact on the sensors, we may divide the space into 4 quadrants centered on this path modification event. For sensors in the top left quadrant, this point that goes from bottom right to top left is now 2 units closer to the sensor. For sensors in the bottom right, it's now 2 units farther away. Otherwise, the sensor is unaffected, since the effect of the y coordinate change is cancelled out by the effect of the x coordinate change. A simple bit of math extends this to the case where you increment y[k] by more than 1.

I claim that after iterating through all 4 sensors and modifying the path, the problem is solved. If one of the sensors is still unsatisfied, then no solution exists. Otherwise, print out the string of Us and Rs. The number of Us is simply y[k+1]-y[k], with the exception of the case when y[0]>0, in which case print those first.

I'm probably not good enough at writing proofs or analysing such things to deliver a rigorous proof that my algorithm solves the problem, but I shall address some possible concerns:

1) It would appear that shifting the path for each sensor would not result in the right answer, because when looking at the top sensors, it might shift the path too high and cause the bottom sensors to be unsatisfied. In fact, this is not entirely the case because the path is shifted only to the point where the top sensor is just barely satisfied. If the bare minimum requirement for the top sensor to be satisfied still nonetheless causes the bottom sensor to become dissatisfied, then it means that no solution exists. Also, to test this, I wrote code to shift down the path (i.e. decrement y[k]) if that happens, but found through experimentation that this was never executed unless there is no solution anyway. This supports my conjecture.

2) It is not obvious that lexical order is preserved. However, it actually is preserved because the loop for incrementing y[k] iterates from right to left. So the rightmost Rs get changed into Us, and this will always make sure that the string is still the lexically optimal one. 

Anyway, here's my code: http://pastie.org/1883698

I look forward to solving more!