A Mazing Problem

Time Limit: 2 Seconds
Memory Limit: 65536 KB

In a maze of size M by N, there is a savage hound named "Fatdog". Fatdog keeps moving around, and will have a good bite at his victim as soon as anyone moves into his sightline. You are supposed to compute the minimum time taken to cross this maze alive, and Fatdog must be for sure avoided.

In every time unit, you may move one block to one of the upper, lower, left and
right neighboring blocks, or you may stay where you are. Of course you must not
move into the wall, neither must you walk right into Fatdog, and you must not
fall into Fatdog's sightline as well. The entrance given is guaranteed to avoid
Fatdog's sight.

At the mean time, Fatdog is not as smart as you are -- in every time unit, he
either moves forward by one block, or stays and turns 90 degrees to the left or
to the right.

Assume that in every time unit you and Fatdog are taking actions simultaneously.

Input

There are several test cases. For each test case:

The first line of input contains 2 integers M and N (0 < M,N <= 50) which
indicating the size of a maze, provided that the origin is at the upper-left
corner.

The second line contains 7 numbers: x1,y1,x2,y2,x3,y3,D where x1 and y1 are
the coordinates of your starting position, x2 and y2 are your exit coordinates,
x3 and y3 are the coordinates of the initial position of Fatdog (assuming that
he is facing North at every beginning)

The next line contains D(0 < D <= 50) characters, representing Fatdog's
actions. When he finishes these D actions, he will be back to his starting position
and facing North, and then he will repeat these actions again and again forever
(poor Fatdog...). These characters are:

'G' means moving one block forward

'L' means turning 90 degrees to the left

'R' means turning 90 degrees to the right

Then there will be M lines followed, with N characters in each line, describing
the maze:

'.' represents an empty block, meaning there is a path.

'*' represents a block of wall.

The input is finished by a pair of 0's as M and N.

**Output**

For each test case, the first line of output must be in the form "Case d:" where
d is the case number (start counting from 1). The second line must be either
"Minimal time is: d" where d is the minimum crossing time, or "No way out" meaning
that it is impossible to cross the maze alive.

Two test cases must be separated by a blank line.

Sample Input

5 3
3 1 3 3 4 2 8
GGRRGGRR
***
*.*
...
*.*
***
5 3
3 1 3 3 2 2 2
LR
***
*.*
...
*.*
***
3 3
2 1 2 3 2 2 4
RRRR
***
...
***
0 0

**Sample Output**
Case 1:
Minimal time is: 3
Case 2:
Minimal time is: 2
Case 3:
No way out

Source:

**Zhejiang University Local Contest 2002**
Submit
Status