Connection Status:
Competition Arena > SlimeXResidentSlime

SlimeXResidentSlime

SRM 506 · 2010-11-01 · by dolphinigle

SRM 506 · 2010-11-01 · by dolphinigle · Brute Force, Graph Theory, Search
Class Name: SlimeXResidentSlime
Return Type: int
Method Name: exterminate
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{
"#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",
"1"}
Returns: -1

It's impossible to defeat this level. Each time you kill a slime, the other slime gets revived.

2)
{
"$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.

3)
{
"..999..",
".99999.",
".99$..."}
Returns: -1
4)
{
"..999..",
".9999..",
".99$..."}
Returns: 9

Submissions are judged against all 167 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SlimeXResidentSlime with a public method int exterminate(vector<string> field) · 167 test cases · 2 s / 256 MB per case

Submitting as anonymous