No left turns
A person in a maze needs to navigate from one cell to another. They can move to an adjacent cell in one of four directions: up, down, left, or right. However, there are specific restrictions on their movement. The initial direction can be chosen freely, but after that, they cannot turn back 180° or make left turns (90° counterclockwise). Only 90° clockwise turns are allowed. Additionally, they cannot move outside the maze's boundaries.
Write a program to determine the shortest valid path between the specified cells.
Input
The first line contains two integers M and N (1 ≤ M, N ≤ 1500), representing the dimensions of the maze. This is followed by M lines, each containing N characters, which describe the maze. The character "*" represents a wall (movement into this cell is not allowed), "." indicates a free cell, "S" marks the starting cell, and "D" marks the destination cell. The starting and ending cells are free and appear exactly once.
Output
Output a single line containing the shortest sequence of moves that takes the person from the starting cell to the destination cell, adhering to the movement rules. Use "U" for moving up, "D" for down, "L" for left, and "R" for right. If reaching the destination cell without violating the rules is impossible, output "NO SOLUTION" (without quotes).