JOIN
Get Time

   Problem Statement  

 Problem Statement for EllysChessboard

Problem Statement

    Elly has a standard chessboard, divided into 8 by 8 unit square cells. She wants to place pebbles onto some of the cells. You are given a String[] board. The j-th character of the i-th element of board is '#' if she wants to put a pebble onto the cell (i, j), and it is '.' otherwise.



Initially the chessboard doesn't contain any pebbles. Elly places the pebbles one by one. The cost of adding a pebble is defined as follows. If this is the first pebble to be placed (i.e., the board is empty), it can be placed for free. Otherwise, the cost is the Manhattan distance (see Notes for the definition) to the most distant pebble that has already been placed on the board.



Return the minimal total cost of placing a pebble onto each chosen cell.
 

Definition

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

Notes

-The Manhattan distance between the cell (x1, y1) and the cell (x2, y2) is defined as |x1-x2| + |y1-y2|, where || denotes absolute value.
 

Constraints

-board will contain exactly 8 elements.
-Each element of board will contain exactly 8 characters.
-Each character in board will be either '#' or '.'.
 

Examples

0)
    
{"........",
 "........",
 "...#....",
 ".#......",
 ".......#",
 "........",
 "........",
 "........"}
Returns: 10
Elly wants to put pebbles on three cells: (2, 3), (3, 1), and (4, 7). One of the optimal ways to do this is as follows:
  • First, put a pebble to (2, 3). It costs nothing.
  • Next, put a pebble to (3, 1). It costs |2-3| + |3-1| = 3.
  • Next, put a pebble to (4, 7). The Manhattan distance between (4, 7) and (2, 3) is 6, and the Manhattan distance between (4, 7) and (3, 1) is 7, so the cost is max(6, 7) = 7.
The total cost is 0 + 3 + 7 = 10.
1)
    
{"........",
 "........",
 "........",
 "........",
 "........",
 "........",
 "........",
 "........"}
Returns: 0
2)
    
{".#......",
 "........",
 "..#..#.#",
 "...#..#.",
 "........",
 "...#...#",
 "...#...#",
 "........"}
Returns: 58
3)
    
{"##..####",
 "#####..#",
 "..#.#...",
 "#..##.##",
 ".#.###.#",
 "####.###",
 "#.#...#.",
 "##....#."}
Returns: 275
4)
    
{"########",
 "########",
 "########",
 "########",
 "########",
 "########",
 "########",
 "########"}
Returns: 476

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 577 Round 1 - Division I, Level Two