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
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:
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 

Petar Bosnjak:
20140515 21:03:09
Nice state :)

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 