All submissions for this problem are available.
The legends Firestorm (Martin Stein), Heatwave(Mick rory) and Atom (Ray Palmer) are caught by Vandal Savage's men. Vandal Savage decides to torture Heatwave and Atom because by doing so, Stien can be forced to create the Soviet Firestorm. Rip Hunter being the Captain of the mission has to do something to save them. Somehow with the help of Gideon, Rip Hunter got the map of the prison. Hunter plans for a way to help all three. Unfortunately, Martin Stein is under tight security. So, Hunter decides to rescue Atom and Heatwave first and then with the help of the full team, he can save Stein.
The prison looks like a "n x m" matrix from top. It consists of n * m cells with each cell being one of the following:
i) A wall through which one cannot walk through. It is indicated by '*'
ii) Empty space through with one can walk through. It is indicated by '.'
iii) One of the two members (Atom/Heatwave) who needs to be saved. It is indicated by '$'
iv) Vandal Savage's man (Enemies). It is indicated by '#'
Recently Chay Ara was becoming unstable. She couldnt control the anger on people who fought against her. She started killing them. Rip asks Black Canary to train Chay Ara. Now that Chay Ara is well trained. So, Rip Hunter sends Chay Ara to the rescue mission advising her not to kill anyone unless it is actually required. Chay Ara accepts the mission. Chay Ara doesn't know where to enter the building. And also, from a cell (x1, y1), Chay Ara can move to the cell (x2, y2) iff abs(x2 - x1) + abs(y2 - y1) == 1 and 1 <= x2 <= n and 1 <= y2 <= m. Now you are the Gideon. Keeping the two things in mind, Set a course such that Chay Ara saves both of them killing minimum number of enemies.
Note: Your route must include the path Chay Ara uses to enter the building, pick both of them and leave the building.
The first line consists of 't', the number of test cases.
The first line of each test case consists of two integers 'n' and 'm', the dimensions of n x m prison.
Next 'n' lines each consisting of 'm' characters represent the prison.
It is always guaranteed that there is a way from outside which leads to both of them.
1 <= t <= 100
2 <= n, m <= 100
For each testcase, output the minimum number of enemies Chay Ara kills while saving both of them.
Input: 1 5 10 ****#***** *..#.#..** ****.***** *$#.#.#$** ********** Output: 4
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.