TopCoder problem "MountainMap" used in SRM 369 (Division I Level Three)



Problem Statement

    

A mountain map is a NxM rectangular grid where each cell has a height. The heights are positive integers between 1 and N*M, inclusive, and no two distinct cells have equal heights. Two cells are called neighboring if they share a side or a corner. A cell is called locally minimal if its height is less than the heights of all its neighboring cells.

You are given a String[] data. The j-th character of the i-th element of data is 'X' if the j-th cell in the i-th row of the mountain map is locally minimal, and '.' otherwise. Calculate the number of distinct mountain maps that match the data. Return the result modulo 12345678.

 

Definition

    
Class:MountainMap
Method:count
Parameters:String[]
Returns:int
Method signature:int count(String[] data)
(be sure your method is public)
    
 

Constraints

-data will contain between 1 and 4 elements, inclusive.
-Each element of data will contain between 1 and 7 characters, inclusive.
-All elements of data will contain the same number of characters.
-Each character in each element of data will be '.' or uppercase 'X'.
 

Examples

0)
    
{".X."}
Returns: 2
The middle cell is lower than its neighbors, so its height is 1. There are two variants of heights for the other cells: the left cell's height is 2 and the right cell's height is 3, or vice versa.
1)
    
{"X.",
 ".X"}
Returns: 0
No two neighboring cells can both be locally minimal, so the answer is 0.
2)
    
{"...",
 "..."}
Returns: 0
Each mountain map contains at least one locally minimal cell.
3)
    
{"X.",
 "..",
 ".X"}
Returns: 60
4)
    
{"X.X",
 "...",
 "X.X"}
Returns: 4800
5)
    
{"..X.."}
Returns: 6
6)
    
{"....X.",
 "......",
 ".X...X"}
Returns: 869490

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10785&pm=8041

Writer:

ivan_metelsky

Testers:

PabloGilberto , Yarin , Olexiy

Problem categories:

Brute Force, Dynamic Programming, Simple Math