CHMAZE - Changing Maze

Luke Skywalker and his sister/love interest Leia are trying to get through a killer maze. And I mean killer! Every time step, the boundaries change. If our twins/lovebirds ever visit a square the same time a boundary appears, they’re toast. There is no need to panic; the Force will guide them through the maze, and they will not die. However, the Force needs to know what advice to give and is therefore asking you for help.

Luke and Leia begin in the northwest corner of a maze. They want to make it to the southeast corner of the maze. At any given time step, Luke and Leia can move one square north, south, east, or west, or they can stay where they are. At every time step, the boundaries of the maze change: there is a finite list of patterns; if Luke and Leia are still in the maze when the list of patterns is exhausted, the maze cycles through again from the beginning of the list. You need to compute whether Luke and Leia can make it to the southeast corner of the maze, and, if so, the minimum number of time steps necessary for them to get there. Remember, the Force is counting on you! If you give the Force bad advice, we’ll have to wait around for A Newer Hope and Force Knows how long that could take!

Input

The input consists of several test cases. Each case (but the last) will begin with a line containing three decimal integers. The first is the number of rows in the maze; the second is the number of columns in the maze; the third is the number of patterns in the list. The first two numbers will be inclusively between 1 and 20; the third will be inclusively between 1 and 10. The integers will be separated by exactly one space and will be followed by one <EOL>. Immediately following this line will be a number of patterns, equal to the number specified on the first line. Each pattern will consist of r lines each containing c characters, where r is the number of rows and c is the number of columns indicated on the first line. Each character will be either 0 (indicating no boundary) or 1 (indicating a boundary). Each line will be terminated by <EOL>, and an extra <EOL> will follow each pattern. The northwest corner of the first pattern will always be zero, since Luke and Leia will be starting from there. The last case will be three zeros, separated by exactly one space and followed by exactly one <EOL>. This case is not to be processed; it indicates the end of input.

Output

The output cases are to appear in the same order in which they appear in the input. Each output case should be of the form Case c: Luke and Leia can escape in s steps. or of the form Case c: Luke and Leia cannot escape. c and s are decimal integers. c in the number of the case being processed (starting with 1) and s is the minimum number of time steps Luke and Leia require to reach the southeast corner. Each line should be terminated by exactly one <EOL>.

Example

Input:
5 5 1
00000
00000
00000
00000
00000
5 5 2
00000
00000
00000
00000
00000
01110
01110
11111
01110
01110
0 0 0

Output:
Case 1: Luke and Leia can escape in 8 steps.
Case 2: Luke and Leia cannot escape.

Added by:Daniel Gómez Didier
Date:2008-11-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:2007 U.Nacional - Circuito de Maratones ACIS / REDIS

hide comments
2009-07-31 18:01:45 majid
thx ":D"
I got NZEC 3 times because of EOL :(
If u code by java use scanner ...
2009-07-07 07:11:09 :D
I really admire people who did this one at the first try. First of all You can access a field even if it's occupied at a given turn, only next turn status count. Second: the problem states there's an extra EOL and there seems to be in test data, so don't be fooled by the example :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.