TopCoder problem "CheapestIsland" used in SRM 312 (Division I Level Three)



Problem Statement

    

You are given a rectangular grid, each cell containing an integer (not necessarily positive) number, denoting its cost. Find the cheapest connected set of cells (possibly empty), and return its cost. The cost of the set of cells is defined as the sum of the costs of its cells. A set is connected if you can get from any cell of the set to any other cell of the set by moving between adjacent cells of the set. Two cells are adjacent if they share a side (so each non-border cell has four adjacent cells).

The grid is given as a String[] cells, where each element contains a list of single-space separated integers. Each element of cells represents a row of the grid from left to right, and the rows are ordered from top to bottom.

 

Definition

    
Class:CheapestIsland
Method:minCost
Parameters:String[]
Returns:int
Method signature:int minCost(String[] cells)
(be sure your method is public)
    
 

Constraints

-cells will contain between 1 and 9 elements, inclusive.
-Each element of cells will contain between 1 and 50 characters, inclusive.
-Each element of cells will contain between 1 and 9 integers, inclusive, separated by single spaces.
-All elements of cells will contain the same number of integers.
-Each integer in cells will be between -1000 and 1000, inclusive, and contain no extra leading zeroes.
 

Examples

0)
    
{"-10 1", 
"2 -10"}
Returns: -19
To connect both -10's, we need to choose between 1 and 2, and 1 is obviously better.
1)
    
{"1 2 3", 
"4 5 6", 
"7 8 9"}
Returns: 0
No need to take any cell here, as they are all positive.
2)
    
{"-5 100 -5", 
"-5 100 -5"}
Returns: -10
Sometimes it's not good to take all the negative numbers.
3)
    
{"-1 -1 1 -1 -1",
"-1 -1 1 -1 -1",
"-1 -1 1 -1 -1",
"99 99 99 99 99",
"-1 -1 -1 -1 -1",
"-1 -1 -1 -1 -1"}

Returns: -11

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9992&pm=6482

Writer:

Petr

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Dynamic Programming