TopCoder problem "AmoebaDivOne" used in SRM 493 (Division I Level Three)



Problem Statement

    Little Romeo likes cosmic amoebas a lot. He has a colony of all kinds of amoebas. Recently he received a rectangular table as a gift from his mother. He decided to place one of his amoebas on it. The table is a grid of square 1x1 cells, and each cell is occupied by either matter or antimatter. The usual shape of a cosmic amoeba is a convex set of cells (see explanation below). Romeo can place it on the table 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.



A set of cells is called connected if there exists a path between each two cells from the set which satisfies the following restrictions:
  • All cells in the path belong to this set.
  • Each pair of neighboring cells in the path shares a common edge.
A set is called convex if it is satisfies the following conditions:
  • It is connected.
  • If any two cells in the set lie in the same row then all cells in that row between them also belong to the set.
  • If any two cells in the set lie in the same column then all cells in that column between them also belong to the set.

You are given a String[] table containing only lowercase hexadecimal digits. Numbers 0-9 are represented by characters '0'-'9', and numbers 10-15 are represented by characters 'a'-'f'. Each digit in table represents a 2x2 section of the table. For each digit table[i][j], let n be its 4-digit binary representation. From this, you can determine the contents of the following cells:

row 2*i, column 2*j: n[0]

row 2*i, column 2*j+1: n[1]

row 2*i+1, column 2*j: n[2]

row 2*i+1, column 2*j+1: n[3]

where 0 represents antimatter, and 1 represents matter. For example, if table[0][0] = '5', then its 4-digit binary representation is "0101" (bits are numerated from right to left), and that section of the table looks like this: 

      |  column 0  |  column 1  |
------|------------|------------|
row 0 |   matter   | antimatter |
------|------------|------------|
row 1 |   matter   | antimatter |
------|------------|------------|
Now Romeo wonders how many ways there are to place a single amoeba on the table. Return this number modulo 1000000007. 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:AmoebaDivOne
Method:count
Parameters:String[]
Returns:int
Method signature:int count(String[] table)
(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 in table will be a hexadecimal digit ('0'-'9', 'a'-'f').
 

Examples

0)
    
{"0"}
Returns: 13
Here are all 13 configurations, where X represents the amoeba: 
X. .X .. .. XX .. X. .X XX XX X. .X XX
.. .. X. .X .. XX X. .X X. .X XX XX XX
1)
    
{"84","21"}
Returns: 72
Here the table looks like this ('.' stands for cell with antimatter and '#' stands for cell with matter): 
....
.##.
.##.
....
2)
    
{"e","e"}
Returns: 2
3)
    
{"00"}
Returns: 90

Problem url:

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

Problem stats url:

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

Writer:

K.A.D.R

Testers:

PabloGilberto , ivan_metelsky , maksay

Problem categories:

Dynamic Programming