Connection Status:
Competition Arena > PoisonedSwamp

PoisonedSwamp

SRM 800 · 2021-02-08 · by misof

SRM 800 · 2021-02-08 · by misof · Graph Theory
Class Name: PoisonedSwamp
Return Type: String
Method Name: cross
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are about to cross a poisoned swampy area. Luckily, you have its map: the String[] swamp containing a rectangle of characters. Each character represents one unit square of the swamp as follows:

  • '.' is a safe square, you can step on it.
  • '#' is a blocked square, you cannot step on it.
  • '1'-'9' are poisoned squares. Stepping on a square with digit X increases your poison count by X.
  • 'S' is a spring with cleansing water. Stepping on it resets your poison count back to zero.

You start in the top left corner of the map (row 0, column 0) and your poison count is 0. You want to reach the bottom right corner of the map. You move in steps. In each step you can move from your current square to another square that shares a side with your current one. You may not leave the mapped area. If your poison count reaches 10 or more, you die.

You ARE allowed to enter the same square multiple times. If you step on the same poisoned square multiple times, you get the corresponding amount of poison each time you do so. If you step on the same spring multiple times, you get cleansed each time you do so.


Return "possible" if you can cross the swamp alive and "impossible" if you cannot do so.

Constraints

  • swamp will contain between 2 and 20 elements, inclusive.
  • Each element of swamp will contain the same number of characters, and that number will be between 2 and 20, inclusive.
  • Each character in swamp will be one of ".#123456789S" (quotes for clarity).
  • The characters in the top left and bottom right corner of swamp will be '.'.
Examples
0)
{".....",
 "####.",
 ".....",
 ".####",
 "....."}
Returns: "possible"

There's no poison, just find your way across.

1)
{".....",
 "####.",
 "97...",
 "9#2##",
 "97..."}
Returns: "possible"

There is a strongly poisoned area in this swamp but luckily it can be avoided completely by taking a shortcut and only receiving 2 poison.

2)
{".111111111.",
 ".#########.",
 "..22222...."}
Returns: "possible"

If you go down and right, you'll eventually collect 10 poison and die. Luckily, if you go right and then down, you'll only collect 9 poison and you'll reach the end of the swamp alive.

3)
{".#222#111",
 "4#S#2#1#S",
 "4#3#S#1#9",
 "S33#111#."}
Returns: "possible"

A lot of poison in this swamp, but luckily for us the cleansing springs are frequent enough to get us through.

4)
{"..111111111111..",
 "###############."}
Returns: "impossible"

Too much poison along this way.

5)
{"..111111111111..",
 "#######S#######."}
Returns: "possible"

This example shows that sometimes we need to revisit the same cell. In this case, the only way to cross the swamp is to make a detour: after you have 6 poison, step down to reach the cleansing spring and then return back and continue. You will reach the end of the swamp alive (with 7 poison) if you do so.

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

Coding Area

Language: C++17 · define a public class PoisonedSwamp with a public method string cross(vector<string> swamp) · 48 test cases · 2 s / 256 MB per case

Submitting as anonymous