TopCoder problem "Socialize" used in TCI '02 Round 4 (Division I Level Two)



Problem Statement

    

At a recent party, a number of people were loitering around talking to one another, and generally doing partyish things. It was a very social event, and we would like to come up with some sort of a metric for how social it was. One possibility is to find the shortest distance from each person to every other person, and take the average. Your task is to write a class Socialize, with a method average, that computes the average distance between all distinct pairs of people, and returns this average, rounded to the nearest integer (.5 rounds up).

However, our metric would not be very accurate if we just took the distance between people. For example, two people could have been only a few feet from each other, but if there was a wall between them, they wouldn't have been able to socialize. Thus, we will define the distance between two people as the shortest path between them, which doesn't go through any obstacles, and where the path goes in discrete steps, with each step being one unit in any of the four cardinal directions (east, west, north and south).

Because there are various obstacles, there may be cases where two people are totally cut off from each other. In this case, you should not include the distance between them in your calculation.

For example, if the layout were ('P' represents a person, '#' represents some sort of an obstacle, and '.' represents open floor): 

P...P
###..
P...#
####P

There are four people in total, one at each of the following locations (where the first coordinate is the distance along the x axis, and the second is along the y axis, with (0,0) at the upper left corner): (0,0),(4,0),(0,2),(4,3)

The person at (0,0) and the person at (4,0) are connected by a path of length 4.

The person at (0,0) and the person at (0,2) are connected by a path of length 8 because to get from one to another, they have to walk around the obstacle between them.

The person at (4,0) and the person at (0,2) are connected by a path of length 6.

The person at (4,3) can not reach any of the other people because he is blocked in (no diagonal movement), thus distances from him to other people do not play a role in the average.

Thus, there are three paths between people, whose lengths are 4,6, and 8. The average length of these paths is 6, so your method should return 6.

 

Definition

    
Class:Socialize
Method:average
Parameters:String[]
Returns:int
Method signature:int average(String[] layout)
(be sure your method is public)
    
 

Notes

-If there are no pathes between people, return 0.
 

Constraints

-layout contains between 1 and 50 elements, inclusive.
-each element of layout contains between 1 and 50 characters, inclusive.
-each element of layout will contain the same number of characters.
-each character in layout is either '#', '.', or 'P'.
 

Examples

0)
    
{"P"}
Returns: 0
1)
    
{"#"}
Returns: 0
2)
    
{"P#P"
,"P#."
,"P#P"}
Returns: 2
3)
    
{"P...P",
"###..",
"P...#",
"####P"}
Returns: 6

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4355&pm=1011

Writer:

lars2520

Testers:

alexcchan , lbackstrom

Problem categories:

Graph Theory, Search