TopCoder problem "AmoebaDivTwo" used in SRM 493 (Division II Level One)



Problem Statement

    

Little Romeo likes cosmic amoebas a lot. Recently he received one as a gift from his mother. He decided to place his amoeba on a rectangular table. The table is a grid of square 1x1 cells, and each cell is occupied by either matter or antimatter. The amoeba is a rectangle of size 1xK. Romeo can place it on the table in any orientation as long as every cell of the table is either completely covered by part of the amoeba or completely uncovered, and no part of the amoeba lies outside of the table. It is a well-known fact that cosmic amoebas cannot lie on top of matter, so every cell of the table covered by the amoeba must only contain antimatter.



You are given a String[] table, where the j-th character of the i-th element is 'A' if the cell in row i, column j of the table contains antimatter or 'M' if it contains matter. Return the number of different ways that Romeo can place the cosmic amoeba on the table. Two ways are considered different if and only if there is a table cell that is covered in one but not the other.

 

Definition

    
Class:AmoebaDivTwo
Method:count
Parameters:String[], int
Returns:int
Method signature:int count(String[] table, int K)
(be sure your method is public)
    
 

Constraints

-table will contain between 1 and 50 elements, inclusive.
-Each element of table will contain between 1 and 50 characters, inclusive.
-All elements of table will have the same length.
-Each character of each element of table will be either 'A' or 'M'.
-K will be between 1 and 50, inclusive.
 

Examples

0)
    
{"MA"}
2
Returns: 0
The amoeba requires a 1x2 or 2x1 rectangle containing only antimatter, but there is no such space available on the table.
1)
    
{"AAA",
 "AMA",
 "AAA"}
3
Returns: 4
2)
    
{"AA",
 "AA",
 "AA"}
2
Returns: 7
Here are all 7 configurations, where X represents the amoeba: 
XX .. .. X. .X .. ..
.. XX .. X. .X X. .X
.. .. XX .. .. X. .X
3)
    
{"MMM",
 "MMM",
 "MMM"}
1
Returns: 0
There are no cells with antimatter at all.
4)
    
{"AAM",
 "MAM",
 "AAA"}
1
Returns: 6
5)
    
{"AAA",
 "AAM",
 "AAA"}
2
Returns: 9

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14422&pm=11178

Writer:

K.A.D.R

Testers:

PabloGilberto , ivan_metelsky , maksay

Problem categories:

Brute Force, Simple Search, Iteration