| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem G
Save the Princess
Time Limit: 1000ms
Memory Limit: 65536kb Description
Stois is a hard-working but shy student in USTC. On day his dear princess in library study room was caught by bad senior schoolfellow, he intended to save the princess to show his love.  Each round he could go around (up ,down ,left, right). Some rules he kept in mind were below: If the place he occupied was slime or snake, he would die; If the place he occupied was a boat or a sword, he would take it always; If the place he occupied was where the princess was jailed, then he would save her successfully; He could also kill the slime or snake around him in one round, then the place became empty; At first he can only beat the slime, then if he got the sword, he can beat snake; He cannot stand on the river, only when he got a boat; Please help Stois find the minimum round to save princess. In return, he would recommend a MeiZhi for u. Input
The input consists of several test cases, and each case indicates a map for Stois. The first line of each test case contains two integers M and N (2 <= M, N <= 300). Each of the following M lines contains N uppercase letters, each of which is one of 'Y' (Stois), 'P'(princess), 'S' (snake), 'L' (Slime), 'R' (river), 'W' (sword), 'B' (boat) and 'E' (empty space). Both 'Y' and 'P' appear only once, 'B' and 'W' appear at most once. A test case of M = N = 0 indicates the end of input, and should not be processed. Output
For each test case, please output the turns you take at least in a separate line. If you can't arrive at the target, output "-1" instead.
Sample Input
3 4 YLEL EERE SSPE 5 5 YEEER ESSRR BSSSP RRRRR EEEEE 0 0 Sample Output
8 8 |