Land Mines of Byteland
All submissions for this problem are available.
Little Joe is stuck in a rectangular field containing some land mines. The field is a grid of squares. Some squares are free while some contains a wall. The squares having an exit are marked with X. Some of the squares contain a land mine or a switch. A switch is used to defuse the land mine. There are four different types of switches and mines: red, green, yellow and blue. Each switch can only defuse the mine of the same color. Movement is allowed only in adjacent free square horizontally or vertically. Joe can also move on the square containing a switch. If a square has a land mine he can move on it only if he has stepped on a square containing a switch of the same color before. He cannot go across walls or step outside the field. He can only leave the field through exit squares. If he cannot reach an exit square or if no exit squares are present, he is trapped.
Help Joe in calculating the minimum number of steps required to reach the exit node. One step is denoted by number of movements in the adjoining squares.
The first line of the input contains a number t (1=< t< =100) denoting the number of test cases. Each test case contains:
The first line containing two integers m and n (1<= m, n <=100) specifying the size of the field. Then there are m lines each containing the n characters. Each character is one of the following:
Dot '.' Free square
Hash mark '#' Wall
Asterisk '*' Joe's starting position
Uppercase letter 'R','G','Y','B' Land mine of Red, Green, Yellow or Blue color
Lowercase letter 'r','g','y','b' Switch of red, green, yellow or blue color
Uppercase X 'X' Exit
The field can have more than one exit or no exit at all. There can be multiple land mines and/or switches of the same color. Some switches may not have a corresponding mine and some mines may not have a corresponding switch. There will be exactly one '*' in each field.
For each test case, output one line containing an integer corresponding to the minimum number of steps required to reach an exit square. If no exit square are reachable print -1.
Input: 3 1 10 *........X 1 3 *#X 3 20 #################### #XY.gBr.*.Rb.G.GG.y# #################### Output: 9 -1 45
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.