LumberjackHack

SRM 186 · 2004-03-13 · by Eeyore

SRM 186 · 2004-03-13 · by Eeyore · Graph Theory, Search, String Parsing

Show categories

Class Name: LumberjackHack

Return Type: int

Method Name: timeToShore

Arg Types: (vector<string>)

Problem Statement

If you've driven much on North American highways, especially west of the prairies, you're familiar with the sight of trucks hauling great stacks of logs. In the old days, before internal combustion was a going concern, logs were transported at a more sedate pace by floating them down a river. This was all very picturesque until the logs jammed together so tightly that no movement was possible. Then they had to send someone out on the river to loosen up the works with dynamite. Skipping nimbly from log to log, a lumberjack would find the crux of the logjam and set an explosive charge. After lighting the fuse, he had to skip quickly back to shore. The lumberjack was prepared to plunge briefly into the river as a shortcut, but he really didn't like to get wet. The main thing was to get away quickly.

You are given a String[] describing a stretch of river in which the character '|' stands for a log, '.' stands for water, and '+' is where the lumberjack is standing on a log. The lumberjack can reach safety by stepping up, down, left, or right between adjacent logs until he reaches the far left or far right, at which point he is immediately safe from the blast. (The "far left" is the first character in each String, and the "far right" is the last character in each String.) Stepping up or down onto a log takes him one second, while stepping left or right onto a log takes two seconds. The lumberjack may step on no more than one square of water in his entire trip, at a cost of three seconds instead of the usual one or two. Return the minimal number of seconds it will take the lumberjack to reach safety, or -1 if he cannot do so.

Constraints

riverMap contains between 1 and 50 elements, inclusive
the first element of riverMap is between 3 and 50 characters long
every element of riverMap has the same length as the first element of riverMap
for every element of riverMap, each character must be '|', '.', or '+'
riverMap contains exactly one occurrence of the character '+'

Examples

{".+.",
 "||."}
Returns: 3

The lumberjack can reach safety in 1+2 = 3 seconds by stepping down and to the left.

{"..+",
 "||."}
Returns: 0

The lumberjack is already safe at the right edge.

{"....|||",
 "....|..",
 "...||..",
 "||.+...",
 "...|...",
 "...||||"}
Returns: 7

The lumberjack could reach the upper right corner in 1+2+1+1+2+2 = 9 seconds or the lower right in 1+1+2+2+2 = 8 seconds, but his best choice is to reach the left border in 3+2+2 = 7 seconds.

{"||.|....",
 "........",
 ".|.+|..|",
 "...|....",
 "|..|.|.|"}
Returns: -1

The lumberjack had better not light that fuse.

{"||||.|||||||||||.||||||..||.|||..|||||.|.||.||.|.|", "||.|||||.|||.|||.|||||||||||...||||||.|.||||||.|||", "||.|||||.|||||.|.||..||||||||||||..||.|.||||||||.|", "|||||||||||.||||||.|||||||||..|||.|||.|.|.||||||||", "|||..|.||||||||||.||.|||||||||.|.|||||||||||.|||.|", ".|||||||.|||||||||.||..||||||||||||..|.|..||||||||", "|||.|.|.|.||.|||||||...||.||.|||||||.|||||||.|.|||", "|||.||||.|||||||.||||||||.||.||||.||.||||||.||..||", "||||||||||.|...||||||||.||.|||||||.|.||||.||||||.|", "|||||||..|.||.||.|||||||||||.||||||||||.|||.||..||", "||.|.|||||||||||||||||||||||.|.|||||||.||||.|||.||", "|...|||.||||..||.||..||||.|.||.|...|||.||.||.|||.|", "||.|||......||||||||.||||.|||.|||||..||||||.|||||.", ".|||||||.|||||||.||...||||.||||||..||||||||..|||||", "|.||||.||||..|.||.|...|||..||.|.||||.||||||.||||||", "|||||||.|..|.||.|.|||||.||.||.||.||||||.||||||||||", "|||||.||.|||.|.||||||..||||||||..|..||||||||||.||.", "|||.||||||||.|||||||||.||.|||||.||||||||||.|||||||", "|.|||||..||.|||||||||.|||||||||..|.||...||||||||..", "||||||.|...||.||.||||.|||||.|||||||.||||.|||||||.|", "|.||||.||.||..||||||||||.|||||||.|||||||.|.|||||||", "|||||.||||||||.||||||||||||||||||....||.||||||.|||", "||||.||||..||..||||||||.||||||.||.|||.||.|..|...||", "|.||||||||.||.||||||||.|||||||||.|||||||||||||..||", "||.|||..||||..|||||||...|.||||..|.||.|||||||.|.|||", "..|||.||||||||||.||..|.|.|.||||||||..||.||..||||||", "||||||||||.||.||.|||||.||.||||.|||||||.|.|||.||.|.", "|.|||.||.|||||||.|||||||||||||||.||||.|.|.||.||.||", "|||...||||.|||||..||||||||||..|||.|||.||||.|||||.|", ".|..|||||||||||||||.|||.||....|||..|||||||...|||||", "|.|||||.||||||||||||||..|||.||.|.||||.||.|||||||||", ".|||||||||.||||||||..||||.||||||.||||||..|||||||.|", ".||||||.|.|||||..|.|||||||||||||.|.|||||||.||||.||", "|.|||||||.|||||.|.||.|||||..|.|.|||||.||||.|.|.|.|", "|||..||..|..|||.||.|+|||||||||||||.||.|||.||||||||", "|||||||.|.||||||..|||||.|.|||||.|||||||||||||||.||", ".|||...|||||...|||..||||.|.|..|.|||.|.|||||.||||||", "...||||||||||.||.||||....|||||.||.|||||||.||||.||.", ".|||||||||.|.|.||.|||.||.|.|.||||.||||||||||.|||||", "||||..|.|||.||.|...|.|.||||.|.||.||||||..||.||||||", ".||.|||||||...||.|||||||||.|||.||||||||||.|||||||.", "|||||..||||||||.||.|||.|.|||.||||.|.|.||||||||||||", "||||||||||||||.|||.||..|||.||||||||.|.|||||.||||||", "||||.|||||||||.|...||||...|||.||.||||.|..|||.|...|", "||||..|||.||||||.|.....||||.||.||||..||||||.||||||", "|||||||.|||||.||||||.|.|.||||||||.|||||.|..||..|||", "||||..|||.|||||..|||||.|||.||||||.|||||||..||.||||", ".|...|||.||||.|||||||..|.|||||.|||||||||||||.|.|.|", "|||..|.|.|||||||||||||||.||||.|..|||.|||..|||||.||", "|||.|||..|||||.||.|||||.||||.||||||...||||||.|||.|"}
Returns: 48

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

Coding Area

Language: C++17 · define a public class LumberjackHack with a public method int timeToShore(vector<string> riverMap) · 110 test cases · 2 s / 256 MB per case