SUSY - Helping Susy

Susy is a beautiful and smart student. She is an expert  solving puzzle games, specially mazes, and such talent has given her several prizes from various competitions, where her speed and skills are tested.

Right now, she is participating in an special puzzle contests, and her jealous rival, Angelica, is participating too.

At this moment, they are in a tie, and in order to break this tie the judges have prepared a special round with a special game. The rules of this game are the following:

  • The game consists of a table with walls, like a maze. Also, there are some special objects, the Magic Stones. To win the game, the player must take all the stones present in the table.
  • There are four valid movements: Up, Down, Left and Right. Nevertheless, once the player choose a movement from his current position, he cannot stop moving in that direction until he crash with a wall in the maze. Obviously, the player cannot leave the table, so the limits of the table are considered walls too.
  • As there can be many solutions, the judges want the optimal one, which mean the least number of moves.

This is not problem for Susy, but Angelica is having a really bad time with this game. Jealously, Angelica secretly took Susy's solution and cut it in many pieces (She is not very intelligent. She could copy the solution instead but her anger blinded her).

Time is running out, and Susy doesn't have the time required to solve the puzzle again. Fortunately, the participants can ask a friend to help with just one puzzle, and she knows something the judges don't, your programming skills.

Now, she is calling you! Write a program to solve the maze with the least moves possible! Help Susy!

Input

The input begins with two integer numbers, R and C, the number of rows and columns of the table respectively.

Next, there will be R lines with C characters each, representing the maze. Each maze will contain only following characters:

  • "." - free space,
  • "#" - wall,
  • "S" - initial position of the player,
  • "*" - magic stone.

Output

The output consists of 2 lines. The first must contain one only number S. S is the optimal solution of the game.

The next line consists of S strings separated with a "-". These strings are "Up", "Down", "Left" and "Right". The full string represents the movements done in the optimal solution.

If there is more than one optimal solution, you must print the lexicographically smallest one.

Example

Input:
5 6
*S....
....#.
.##...
**....
.#.*#.

Output:
7
Down-Right-Down-Left-Up-Left-Up

Constraints:

2 <= (r, c) <= 20. There will be no more than 13 magic stones in the maze.

NOTE: There will always be a solution for the given maze.


Added by:Samuel Nacache
Date:2013-03-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem (based on a real game)

hide comments
2013-08-26 05:59:18 (Tjandra Satria Gunawan)(曾毅昆)
Good problem, but input formatting is bad. In some input data there exists some extra whitespace in the first line (before integers R and C), and some in the maze map. (I can't tell the exact location, because need so many experiment).
Edit: Input format problems are fixed!


imho it's better if the problem apply multiple test case in one test data and for this low constraints, better using pyramid cluster. [because I like to compare speed with other user ;-) problem with many 0.00s is boring]

Last edit: 2014-03-14 17:05:53
2013-03-07 13:06:16 Ehor Nechiporenko
Wow! Thanks for this problem!
2013-03-06 06:59:00 Wesley May
Awesome! Thanks for fixing that bug where one of the lines was too short and you had to pad it with periods!

edit: that is why you always need to read the whole line and not character by character

Last edit: 2013-03-06 07:08:54
2013-03-06 05:01:34 Samuel Nacache
Problem is free of bugs now. Enjoy solving it. Thanks to some users for pointing that out
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.