TopCoder problem "SnowPlow" used in TCO10 Round 2 (Division I Level One)



Problem Statement

    

Even though it is June, the city of SnowVille is facing some serious trouble: last night, lots of snow covered all the roads in the city.

The road network looks as follows: There are N important places in the city. The places are labeled 0 through N-1. Each road in the city connects two of these places. Each pair of places is connected by at most one road. Each road can contain one or more car lanes. Each road is bidirectional and the number of lanes is the same for both directions.

Sadly, all the snow plows except for one were already decommissioned for the summer. The one snow plow that is still available is in a depot at place 0.

Whenever the snow plow drives along a road, it is able to clean a single lane going in the direction in which it travels. Hence if you want to clean an entire road with K lanes going in each direction, the snow plow must drive along this road at least K times in each direction.

You are given a String[] roads that describes the road network: If there is no road between places i and j, character j of element i of roads is '0'. The maximum number of lanes a road can have in each direction is 9. If there is a road with k lanes in each direction, character j of element i of roads is 'k' (that is, '1' if there is one lane, '2' if there are two lanes, etc.)

Traversing a single lane of any single road takes the snow plow exactly one minute. Return the least number of minutes in which the snow plow can clean all lanes on all roads. If cleaning all lanes on all roads is impossible, return -1 instead.

 

Definition

    
Class:SnowPlow
Method:solve
Parameters:String[]
Returns:int
Method signature:int solve(String[] roads)
(be sure your method is public)
    
 

Notes

-The snow plow is allowed to drive along a lane it already cleared.
-The road network does not have to be planar.
 

Constraints

-The number of places N will be between 2 and 50, inclusive.
-roads will contain exactly N elements.
-Each element of roads will contain exactly N characters.
-Each character of each element of roads will be between '0' and '9', inclusive.
-roads will be symmetric, i.e., for each i and j: character i of element j of roads will be equal to character j of element i of roads.
-For each i, character i of element i of roads will be '0'.
 

Examples

0)
    
{"010000",
 "101000",
 "010100",
 "001010",
 "000101",
 "000010"}
Returns: 10
The important places are connected as follows: 0-1-2-3-4-5. The only optimal solution is for the snow plow to travel from 0 to 5 and back.
1)
    
{"010000",
 "101000",
 "010100",
 "001020",
 "000201",
 "000010"}
Returns: 12
This time the road between places 3 and 4 has two lanes in each direction. One possible optimal schedule for the snow plow is to visit the places in the order 0,1,2,3,4,5,4,3,4,3,2,1,0, each time using a new lane.
2)
    
{"031415",
 "300000",
 "100000",
 "400000",
 "100000",
 "500000"}
Returns: 28
This time the snow plow can clean all lanes simply by going back and forth between 0 and each of the neighboring places a suitable number of times.
3)
    
{"0100",
 "1000",
 "0001",
 "0010"}
Returns: -1
There is no way to reach the road 2-3, so clearly there is no solution.
4)
    
{"0101",
 "1001",
 "0000",
 "1100"}
Returns: 6
In this case the road network consists of the roads 0-1, 0-3, and 1-3. It can be cleared for example by doing a circle in one direction (0-1-3-0) followed by a circle in the other direction. Note that place 2 remains unvisited.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14280&pm=10946

Writer:

misof

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Graph Theory, Simple Math