The 4th(2009) ACM Programming Contest of HUST  Onsite Contest
From: 20091206 12:00:00
To: 20091206 17:00:00
Now: 20170920 01:09:59
Status: Public
C  Coil Judge
Time Limit: 1s
Memory Limit: 128MB
Submissions: 237 Solved: 60
 Description
 Mortal Coil is a very popular game in the past few months. The game has a rectangular maze with obstacles. You guide a virtual snake.
The game goes like this:
1. Choose a grid as starting point of the snake. (Then the grid is marked blocked)
2. Choose a direction (Above Down Left Right) to let the snake go along it until it is blocked by original obstacles or its own body or the border of the maze. The grid which the snake has ever passed would never allow passing any more.
3. If all the grids is occupied by original obstacles or the snake’s body, you win, otherwise repeat procedure 2 and move on until you win or you haven’t choice to move, i.e. you lose.
Your mission is simple——given a maze and a solution, you are asked to judge whether the solution is correct. If the solution is incorrect, please point out whether it tries to step into forbidden grid, it finishes all steps but doesn’t visit all the free grids or the starting point is valid.
 Input
 The input contains multiple cases ended with EOF.
For each case, first line contains two integers: R, C. (3<=R, C<=10)
The next R lines each contains C characters——‘X’ or ‘.’ .’X’ represents obstacles and ‘.’ represents free grids.
The next line contains two integers: Y, X, i.e. the snake begins at grid (Y, X)
The next line contains a string contains only characters in {U, D, L, R}, meaning “up down left right” in order. Is has at most 1000 and at least 1 characters. This line and the above line describe the solution.
 Output
 For each case output the result in one line.
There are 4 kinds of possible outcomes. You can refer to the Sample Output.
 Sample Input

3 5
.....
.X...
...X.
2 4
ULDRUR
3 5
.....
.X...
...X.
1 1
ULDRUR
3 5
.....
.X...
...X.
2 4
ULDR
3 5
.....
.X...
...X.
2 4
ULDRUL
 Sample Output

Case #1: correct
Case #2: invalid starting point
Case #3: 2 more free grid(s)
Case #4: invalid move at (1,2)
HINT
If there are redundant moves after you won, the solution is considered as invalid move like Case #4.
 Hint
 Source
 Xu Han, HUST Campus 2009