SlimeXResidentSlime | Topcoder Archive

Problem Statement

You are playing a game titled Resident Slime. You will play the role of the hero and exterminate undead slimes.

You are on a level that is represented by an RxC rectangular grid of cells given in String[] field. Rows are numbered 0 through R-1 from top to bottom, and columns are numbered 0 through C-1 from left to right. field[r][c] represents the content of the cell located at row r and column c and is one of the following:

'.' : an empty cell.
'#' : a wall.
'$' : an empty cell where you initially reside.
'1'-'9' : a stationary undead slime whose regenerative power is equal to the digit representing it.

You are going to exterminate all the slimes in this level. Unfortunately, after each slime is killed, it only stays dead for a limited time before it gets revived. Your goal is to get the level into a state where every slime is dead. At that point, they will no longer come back to life. More specifically, the game works as follows.

You start at the cell denoted by '$'.
At the beginning of each turn, you either wait or move to one of the four adjacent cells (those which share a side with your current location). You cannot move to a cell which contains a wall.
Next, if there's a dead slime in your new location, it will get revived.
Next, if your new location is occupied by an undead slime, that slime gets killed. The killed slime will remain in the cell.
Next, each slime is revived if its regenerative power is equal to the number of turns ago it was last killed.
Finally, if at this moment all undead slimes are killed, you win the level. Otherwise, the turn advances and the game continues.

What is the minimum number of turns required to win this level? Return -1 if it is impossible.

Definition

Class:: SlimeXResidentSlime
Method:: exterminate
Parameters:: String[]
Returns:: int
Method signature:: int exterminate(String[] field)
(be sure your method is public)

Constraints

field will contain between 1 and 50 elements, inclusive.
Each element of field will contain between 1 and 50 characters, inclusive.
All the elements of field will contain the same number of characters.
Each character in field will be '.', '#', '$', or '1'-'9'.
There will be exactly one '$' in field.
There will be at least one digit (i.e., a slime) in field.

Examples

```
{
"#1$",
".2."}
```
```
Returns: 3
```
Go down, then go left (killing the slime denoted by '2'). Finally, go up (killing the slime denoted by '1') and since no slime gets revived during this turn, you win the level.
```
{
"$",
"1",
"1"}
```
```
Returns: -1
```
It's impossible to defeat this level. Each time you kill a slime, the other slime gets revived.
```
{
"$124"}
```
```
Returns: 5
```
Go right, kill the slime denoted by '1'. Go right, kill the slime denoted by '2'. (After this, the slime denoted by '1' gets revived). Go right, kill the slime denoted by '4'. Go left, (the slime denoted by '2' immediately revives), and kill the slime denoted by '2'. Go left, kill the slime denoted by '1', and win the level.
```
{"$.#2"
,"#..1"}
```
```
Returns: 6
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.