Dijkstra's algorithm www The poison maze is a square room full of poisonous liquid, every step you go, you get hurt. The maze can be described as an NxN grid. For better understanding of the input data, we define +x direction is RIGHT and +y direction is DOWN. Depending on the density of poison, walking on different grid points results in different amounts of damage. You start at point (1,1) (top left), and there is an exit at the diagonal corner (N, N) (bottom right). The damage at each grid point is given. You need to escape from this maze with as little damage as possible. In this problem, you need to use C/C++ to implement a search algorithm to find a path from (1,1) to (N, N) with the smallest total damage. For each test, please output a file with 2 lines: In the first line, please output 2 integer D, L. D is the smallest possible damage (length of the shortest path), and L is the number of steps of this path. In the second line, please output a string of L- 1 characters, consist of 4 characters: {'U', 'D', 'L', 'R'} (denoting "up", "down", "left", "right") describing every step from (1,1) to (N,N). Sample Input 3 114 514 810 Sample Output 45 RDDR