Mar 8, 2015 06:19 AM
(This post was last modified: Mar 8, 2015 06:20 AM by Deadbyte.)
Programming Challenge | Expert | Task - Magic Forest
I've found a collection of numerous problems from my previous algorithmic competitions. Let's if members on Hack Forums will be able to solve some of them.
Please provide your solutions in C or C++.When you provide me with your solution I will check if your output will match with the original samples from the author of the task or if your solution exceeds the time and memory limit.
These tasks are not for beginners.
Magic Forest
You're the magician currently in the middle of your journey to become a wizzard. Your current obstacle is go through the infamous Magic Forest.
The Magic Forest is a two-dimensional grid consisting of r rows and c columns. Each cell in Magic Forest may contain a tree, or may be vacant. A vacant cell may be occupied by bad magician. Magicians (including you) cannot enter cells with trees. One of the cells is designated as the exit cell.
The initial grid, including your initial position (S), the exit cell (E), the positions of the trees (T) and the initial positions of all other magicians (denoted with numbers from 1 to 9), will be given to you. Here's an example of such grid (from the first example):
[img]http://mendo.mk/task_files/forest.png[/img]
Magicians (including you) may move in the forest. In a single move, magicians may perform one of the following actions:
- Do nothing.
- Move from the current cell to one of the four adjacent cells (two cells are adjacent if they share a side). Note that magicians cannot enter cells with trees.
- If you are located on the exit cell, you may leave the forest. Only you can perform this move — all other bad magicians will never leave the forest by using this type of movement.
After each time you make a single move, each of the other bad magicians simultaneously make a single move (the choice of which move to make may be different for each of the magicians).
Your health is measured in HU (Health Units). At the beginning of the journey your health is 100 HU. If a bad magician is located in the same cell with you at some moment, he can cast a spell and reduce your health for some HUs. Each bad magician can cast his spell on you only once. If at some moment your health becomes 0 HU, then you are dead. Note that the moment you leave the forest, no more bad magicians can cast a spell on you, even if another bad magician moves to the exit cell immediately after that.
You would like to leave the forest. In order to do so, you have to make a sequence of moves, ending with a move of the final type. Before you make any move, however, you post this sequence on your personal virtual idol Blog. Then, you will follow this sequence of moves faithfully.
Print the maximum number of HUs that you could have when you enter the exit cell or print 0 if you cannot enter the exit cell with positive number of HUs assuming that you pick the sequence of moves that minimizes this number. Note that you are not required to minimize the number of moves you make.
Input
The first line of input contains one positive integer T (1 <= T <= 20), the number of test cases.
Each test case starts with a line that contains exactly two integers: r and c (1 ≤ r, c ≤ 1000), denoting the number of rows and the number of columns in Magic Forest. The next r rows will each depict a row of the map, where each character represents the content of a single cell:
- 'T': A cell occupied by a tree.
- 'S': An empty cell, and your starting position. There will be exactly one occurrence of this in the map.
- 'E': An empty cell, and where the exit is located. There will be exactly one occurrence of this in the map.
- A digit (1-9): A cell represented by a digit X means that the cell is empty and is occupied by a bad magician whose spell strength is X.
- '.': An empty cell that is not occupied by any magician
It is guaranteed that it will be possible for you to go from your starting position to the exit cell through a sequence of moves.
Output
For each test case, output the maximum number of HUs that you could have when you enter the exit cell or print 0 if you cannot enter the exit cell with positive number of HUs.
Constraints
Time limit: 3 seconds
Memory limit: 64 megabytes
Examples
Input
2
6 8
4...E.T.
...TTT.1
..3.T...
.TT.T9T.
.8..S.T.
...T..T.
3 5
.....
S.E.1
.....
Output
93
99
For the first example: You cannot reach the exit without meeting with the bad magicians with spell strength of 3 and 4. Note that in this example all bad magicians have different spell strengths, but it is possible that more than one bad magician have same spell strength.
![[Image: dead.gif]](https://image.ibb.co/gSF95a/dead.gif)
![[Image: chain.png]](https://i.postimg.cc/NFnfH9zY/chain.png)
