TopCoder problem "CityBuses" used in TCHS SRM 11 (Division I Level One)



Problem Statement

    

You are given a String[] blocks representing the layout of a city. Each character of each element of blocks represents one city block. A 'B' character represents a bus stop, and a '-' represents all other spaces.

The fare for traveling on the bus is equal to the manhattan distance (difference in X-coordinates plus difference in Y-coordinates, see the first example for clarification) between the starting and ending bus stops. Return the largest possible fare for a trip from one bus stop to another.

 

Definition

    
Class:CityBuses
Method:maximumFare
Parameters:String[]
Returns:int
Method signature:int maximumFare(String[] blocks)
(be sure your method is public)
    
 

Constraints

-blocks will contain between 1 and 50 elements, inclusive.
-Each element of blocks will contain between 1 and 50 characters, inclusive.
-Each element of blocks will contain the same number of characters.
-Each character of each element of blocks will be 'B' or '-'.
-There will be at least two bus stops.
 

Examples

0)
    
{"B--",
 "B--",
 "--B"}

Returns: 4
Starting from the top-left, the coordinates of the bus stops are (0,0), (1,0), and (2,2). The distance is the difference in X-coordinates plus the difference in y-coordinates. So, the distance between each pair of bus stops is as follows: 
(0,0) - (1,0) : 1 + 0 = 1
(1,0) - (2,2) : 1 + 2 = 3
(0,0) - (2,2) : 2 + 2 = 4
The largest distance (thus the highest fare) is 4.
1)
    
{"--B",
 "---",
 "-B-"}
Returns: 3
There's only one route we can take, and it has a distance of 3.
2)
    
{"--B-",
 "B---",
 "-B-B",
 "B---"}

Returns: 5
The largest distance here is from (0,2) to (3,0).
3)
    
{"BB"}
Returns: 1
A short, and unexciting bus ride.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10063&pm=6388

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Brute Force, Simple Math, Simple Search, Iteration