Fuzhou University OnlineJudge 
提示: 欢迎访问OurACM平台。
Problem 1688 Binary land

Accept: 87    Submit: 198
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Daxia liked a game named “binary land” (双企鹅,一款家机游戏) when he was a child. Now, we will solve the problem about this game.
You are in control of two penguins – Gurin (blue) and Malon (pink). Each level is divided more or less in half, with Gurin on the right and Malon on the left. They move the same way in vertical direction, but they move in a mirror image in horizontal direction. That is if you press right, Gurin moves right but Malon moves left, and if you press left, Gurin moves left but Malon moves right. You can press up, down, left and right. If an operation leads the penguin to the wall, the penguin will stay in the original place. Every operation is counted one step.

These two penguins are in love and so your task is to open the cage with the heart on the top of the screen. This cage can be opened only if the penguins are on both sides of it as the following picture (either Gurin on the right or on the left is OK). Now ask you to compute the least steps to achieve it.

Input

Input contains several cases. Each case includes ten lines, each line has fifteen characters. The eighth column is always beginning with one cage with the heart and following nine walls. The wall can't be across but the cage with the heart can be across. The two penguins can be across each other, too. There is a blank line between two cases. The meaning of the characters is:
  • "." is used for road.
  • "#" is used for wall.
  • "G" is used for Gurin (only one, and in the tenth line and ninth column).
  • "M" is used for Malon (only one, and in the tenth line and seventh column).
  • "C" is used for cage with the heart (only one, and in the first line and eighth column).

Output

Ououtput a single line for each of the case. This line should contain either "Case i: d" or "Case i: They can’t break open the cage!", where i is the case number (counting from 1) and d is the minimum steps needed to use.

Sample Input

.......C....... .......#....... .......#....... .......#....... .......#....... .......#....... .......#....... .......#....... .......#....... ......M#G...... .......C....... .###.###.###.## ##.#.#.###.#.#. .......#....... .#####.#.#####. .......#....... ##.#.#.#.#.#.## .......#....... .#############. ......M#G...... ......#C....... .......#....... .......#....... .......#....... .......#....... .......#....... .......#....... .......#....... .......#....... ......M#G......

Sample Output

Case 1: 9 Case 2: 30 Case 3: They can't break open the cage!

Source

FOJ月赛-2009年3月--- daxia

Submit  Back  Status  Discuss