[Login|Register]
Problems

Status

Rank

Problem 1287
Elite VIP
Time Limit: 1000ms
Memory Limit: 65536kb
Description

Very Important Pig (VIP) is an interesting game played on an n × m grid.

There are 4 types of cells in the grid: empty(“.”), dirt(“*”), ladder(“#”) and rock(“@”).

Our VIP(“P”) is running according to following rules:

  • If the VIP is on a ladder:
    • He will move to the right cell if it’s empty or a ladder.
    • Or move to the top cell if it’s empty or a ladder. He won’t do this if the right cell is empty or a ladder.
    • Otherwise, the VIP will stay where he was.
  • If the VIP is NOT on a ladder:
    • He will fall into the below cell if it’s empty.
    • Or move to the right cell if it’s empty or a ladder. He won’t do this if the below cell is empty.
    • Otherwise, the VIP will stay where he was.

The goal of game is to help our VIP go back home(“H”) by digging the dirt. A dirt cell becomes empty after digging, and rocks can’t be destroyed. Your task is to dig the minimum number of cells to achieve the goal.

Input

The input consists of multiple test cases. Each case begins with two integers n and m, indicating height and width of the grid. The next n lines each contains m characters, describing the game map. The characters might be “.”, “*”, “#”, “@”, “P” and “H”, which are explained above. You may assume VIP’s initial position(“P”) and home(“H”) are in empty cells, and there’s exactly one “P” and one “H” in the map. (2 ≤ n,m ≤ 1000)

The input ends with n=m=0.

Output

For each test case, output the minimum number of cells to be dug after “Case x: ”, where x is the case number. If it is impossible to accomplish the game, output “oops” instead.

Sample Input
1 3
P*H
3 5
*#@.H
*#**#
P#***
4 6
P@*#.*
*@#@.H
*@#@.#
*.#@.#
4 5
P....
****@
#*#..
****H
1 2
HP
2 3
@H*
P#.
2 3
@H*
P#*
0 0
Sample Output
Case 1: 1
Case 2: 2
Case 3: 4
Case 4: 1
Case 5: oops
Case 6: oops
Case 7: 0
Hint

Following figure shows VIP’s path(“o”) in case 2:

*#@.o
*oooo
oo***
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 2.3ms with 1 query(s).