TCHS-11-250

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.

import java.util.*;

public class CityBuses {
	
	class Pos {
		int x, y;
		Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public int maximumFare(String[] blocks) {
		List<Pos> stops = new ArrayList<Pos>();
		for (int i = 0; i < blocks.length; i++)
			for (int j = 0; j < blocks[i].length(); j++)
				if (blocks[i].charAt(j) == 'B')
					stops.add(new Pos(i, j));
		int max = -1;
		Pos pi, pj;
		for (int i = 0; i < stops.size(); i++)
			for (int j = i + 1; j < stops.size(); j++) {
				pi = stops.get(i);
				pj = stops.get(j);
				max = Math.max(max, Math.abs(pi.x - pj.x) + Math.abs(pi.y - pj.y));
			}
		return max;
	}
	
}