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.
hide comments
harshh3010:
20210406 16:21:02
Do note that they may stay at the same position and wait for boundaries to change 

nadstratosfer:
20180304 12:24:31
Beware of blanklines in input when solving with Python. There are no whitespaces within the patterns. 

abaar:
20170818 11:41:23
cost 1 wa, forgot char '.' haha , 0.00 sec 

shubham_001:
20170630 14:48:47
easy bfs ,just may be bit difficult in implementing 

lonewolf_1:
20160716 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: 20160716 18:05:33 

hodobox:
20160703 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:
20160531 18:31:30
Can anyone explain why the accepted solution output for these following inputs


Rameshwar:
20160522 08:10:52
The Lannisters like this. ;) 

Param Singh:
20160209 18:49:58
A kinda harder version of this is LASER. 

ayush:
20140616 17:13:34
nice question , feeling satisfied after doing this 
Added by:  Daniel Gómez Didier 
Date:  20081118 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  2007 U.Nacional  Circuito de Maratones ACIS / REDIS 