TopCoder problem "TristripeBacteria" used in TCCC07 Round 3 (Division I Level Two)

Problem Statement

You are given a String[] photo containing a photograph of some bacteria. The bacteria lie in a rectangular grid, and the j-th character of the i-th element of photo represents the content of the cell at row i, column j of the grid. The '.' character represents empty space and the '*' character represents a part of a bacterium. Two non-empty cells a and b belong to the same bacterium if and only if there exists a chain of cells where the first cell is a, the last cell is b, and each pair of consecutive cells in the chain shares a common side.

You are studying a special kind of bacteria called tristripe bacteria. They have a special property: a tristripe bacterium can be formed by exactly three stripes (horizontal or vertical) that possibly intersect and/or overlap. All four bacteria in the picture below are tristripe:

{"........................***...",
 "......*........*.........***..",
 "...******..................***",
 "......*.............*.........",
 ".....**.........******........",
 ".............................."}

Return the number of tristripes in the photo.

Definition

Class:	TristripeBacteria
Method:	howMany
Parameters:	String[]
Returns:	int
Method signature:	int howMany(String[] photo)
(be sure your method is public)

Constraints

photo will contain between 1 and 50 elements, inclusive.

Each element of photo will contain between 1 and 50 characters, inclusive.

Each element of photo will contain the same number of characters.

Each element of photo will contain only the characters '.' and '*'.

Examples

{"........................***...",
 "......*........*.........***..",
 "...******..................***",
 "......*.............*.........",
 ".....**.........******........",
 ".............................."}

Returns: 4

This example is from the statement.

{".....................*********",
 "......*..............*********",
 "...******............*********",
 "......*.........*...*.........",
 ".....**.........******........",
 "....**........................"}

Returns: 2

The leftmost bacterium is not a tristripe.

{"."}

Returns: 0

{"*****************"}

Returns: 1

{"*","*","*","*","*","*","*"}

Returns: 1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10908&pm=8150

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , radeye , Olexiy , ivan_metelsky