TopCoder problem "LumberjackHack" used in SRM 186 (Division II Level Three)



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.

 

Definition

    
Class:LumberjackHack
Method:timeToShore
Parameters:String[]
Returns:int
Method signature:int timeToShore(String[] riverMap)
(be sure your method is public)
    
 

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

0)
    
{".+.",
 "||."}
Returns: 3
The lumberjack can reach safety in 1+2 = 3 seconds by stepping down and to the left.
1)
    
{"..+",
 "||."}
Returns: 0
The lumberjack is already safe at the right edge.
2)
    
{"....|||",
 "....|..",
 "...||..",
 "||.+...",
 "...|...",
 "...||||"}
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.
3)
    
{"||.|....",
 "........",
 ".|.+|..|",
 "...|....",
 "|..|.|.|"}
Returns: -1
The lumberjack had better not light that fuse.
4)
    
{".........|.|.|.|.|..||...||.|..|.||...|.|.|||...||",
 ".||.||...||..|||.....|.||||...|.|.|.|.|..|...|.|||",
 "||.|.|..||.||....|.....|.||.|||||.|.|.||.|||||.|..",
 "|.....|.|.||||.||..|.|..|..|.|||||.....||.|.||....",
 "..|..||...||.|.......|||+||.||||....||||.....|..||",
 "...||..||||.|......||..|.|||||.|.|||||.||..|||...|",
 "|||...|..|..|.|||.||.|..|...||.|||..|..||.|.||....",
 "|..|||||||||.||.....|..|.|.|||||...||...|.|.|||||.",
 ".|..||...|||............|.|..|||.||.|||.||..||.|||",
 ".|.|||...||..|..|...||.||..|..|||||.|.|...||..||.|",
 "||||.|||.|..||||..|..||...|..||.|.||||...|...|.|..",
 ".||..||...|.....|||.|||||..||......|.||.||.|..||..",
 "|.|||....|||||.|..|..|.|||..|.||.||.|.|.|.|..||...",
 ".||.||||||...||||||..||....|..||.|||..||...|.|||||",
 ".||||.|....|...|.||..||..|||.|||||....|...||.|.||.",
 ".|...|..||....||...|.||||.....||||.||.|||||||..|||",
 ".||||...|...|..||...|...|...|.|..|.|.|..|..|||.||.",
 ".|.|||..||||||||........|||||||||.|.|........|||||",
 ".....|...||.||...|||...||||..|||...||....||..||.||",
 "||...||..||.||...||...||||..|.|..|...|||..||..|||.",
 "|..||||.||..|...|....||||||...|||.|.|||||..|||...|",
 ".....|||..||.|||.....||..||||...|||||.||.|.||..|||",
 "|..|.||..|..||..||..|...|..|.||..||||..|...||..|..",
 "||.|..|.|||||...|...|.|..|||||...|.......|.||.||||",
 ".|.....|.|||||.....|||...|..|||||...|.||..||.|||.|",
 ".|...||....|||...|||.||.|.|......|........|.||||||",
 "..|.|.|.|||||..|||..|.........|...|.|.|...||.....|",
 ".|.|.|.|..|.|||||||||||.|.|||....|||||...|.||||.|.",
 "|.|||....|.||||..||......|..|||||.....||.|..||..|.",
 "||.||.|||.|......|..|.|...|..||.|||..||.....|.|..|",
 ".||||..|.|.||||.|||.||.||.....|....|....||...|..||",
 ".....|||...||.||.||....|.||..||....|....|||||.|..|",
 "|.|.|||||...|.||..|..|..|.|..|.|........||..|.|.||",
 "....|..|.|..|.||||||....||||.|.||||||.|.|.|.......",
 "||||....|..|...||..||||||||...|.|||||.|.|||.|...||",
 "|...|.|..|..|..|....|..||..|||....||..||..|..|..|.",
 "|||||....|.||.|..|.||..|||..|.|.|..||.|...|.|..||.",
 "..|.|||.|.||..|...|||.|..|||..||...||...||||.....|",
 "..||||.|.|.....|||..||||..|.||||..|..|||.....||.||",
 "|..|||||....|........|.||||.||..||||.|....|||||||.",
 ".|...||.|.||..|.|....|.||..|.|....|.|.||.||.||.|..",
 ".|..|..|.||||.||||....|||.....|.|...|.|...|...||..",
 "|..|||..|.||.|||..||.....|.|..|.|.|...|.....|.....",
 "||..||.|...|.||...|..|..||.|||.||.|.||...|....|||.",
 ".|....|.|||.|..|||..|.....|.||.||...|...||.......|",
 ".||..|||.|.|....|||...|..|.||.||.|.|...|||||.|.|.|",
 "|.|.||.||.|.|.||.|||.||....||.|||||.||.|.|||......",
 "|...|||...|.||||....|.||.||.|.........|..||.|..||.",
 ".|.....|.|.|....||.||...|||.|..||...||.|||.||.|.|.",
 "||.||.|||.|||..||......|......||..||||.|..||.||||."}
Returns: 63
5)
    
{".+."}
Returns: 3
6)
    
{"..+.."}
Returns: -1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2410

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4750&pm=2410

Writer:

Eeyore

Testers:

lbackstrom , brett1479

Problem categories:

Graph Theory, Search, String Parsing