Lost in a Grid
All submissions for this problem are available.
Zucky wants to find his way out of a maze in minimum possible steps. Zucky knows that he can get lost in the maze if he can't find the exit so he decides to find a way by writing the code first. Now, he knows that there are doors, keys and walls in the maze. Doors and keys can be of four colors Red, Blue, Green, Yellow (RBGY) and red, blue, green, yellow (rbgy) respectively. (Capital letters represent doors, lower case letters represent keys). Every key can open the door of same color as its own. For eg. r can open R, g can open G, etc. No one can get through the walls. Now, being a busy person he can't write all the code. So, he turns to you for help. Your task is to find minimum number of steps in which he can get out of the maze.
Note: Zucky can move only in horizontal and vertical direction.
The first line contains t, the number of test cases (1 = t = 5).
The second line contanis two integers R, C (1 = R, C = 100)
Then R lines follow. Every line contains C characters, which can be
1) R, B, G, Y - doors,
2) r, b, g, y - keys,
3) # - wall,
4) . - free space,
5) * - start point,
6) X - exit
Each line should contain number of steps required if a path exists and "Trapped!" if there is no path.
Input: 2 1 10 *...rRG..X 2 5 *gr## RG..X Output: Trapped! 5
Please note that there can be multiple exits, multiple keys/doors of the same color, multiple walls, but only one start point. Once Zucky collects a key of a particular color, he can use the key to open any number of doors of the same color.
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.