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 . 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 lineas 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 , and an extra 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 . 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 wich 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 .

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.


hide comments
nadstratosfer: 2018-03-04 12:24:31

Beware of blanklines in input when solving with Python. There are no whitespaces within the patterns.

abaar: 2017-08-18 11:41:23

cost 1 wa, forgot char '.' haha , 0.00 sec

shubham_001: 2017-06-30 14:48:47

easy bfs ,just may be bit difficult in implementing

lonewolf_1: 2016-07-16 17:59:38

If anyone is writing in a different language than C++ then be careful b/c there a some test cases that have SPACES in them. Costs me 5 WAs =))

Last edit: 2016-07-16 18:05:33
hodobox: 2016-07-03 01:27:43

@hanstan: At any given time step, Luke and Leia can move one square north, south, east, or west, or they can stay where they are. That means 'staying in one place' also counts as a time step, hence 10 is answer for second case.

hanstan: 2016-05-31 18:31:30

Can anyone explain why the accepted solution output for these following inputs
3 5 6
01000
01010
00010
01000
01010
00010
01000
01010
00010
01000
01010
00010
01000
01010
00010
01000
01010
00000
3 5 6
01000
01010
00010
01000
01010
00010
01000
01010
00010
01000
01010
00010
01000
01010
00010
00000
01010
00010
0 0 0

is

6
10
Shouldn't it be the same?
The first one, they can go to bottom left then go to bottom right-2, then wait until it turns 0, then they can pass.
The second one, they can wait and then go to top right and then to bottom right.
Both should give the optimal solution of 6, right? But it seems that the answer is not the minimum steps needed,yet the fastest one the program found instead...

Last edit: 2016-05-31 18:39:47
Rameshwar: 2016-05-22 08:10:52

The Lannisters like this. ;)

Param Singh: 2016-02-09 18:49:58

A kinda harder version of this is LASER.

ayush: 2014-06-16 17:13:34

nice question , feeling satisfied after doing this

Petar Bosnjak: 2014-05-15 21:03:09

Nice state :)


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