JOIN
Get Time

   Problem Statement  

 Problem Statement for Mountains

Problem Statement

    Manao is developing a simple 2-D computer game. The screen of the game is H pixels high and W pixels wide (1 <= H, W <= 50).



Manao is currently working on the background which should be filled with N mountains (1 <= N <= 10). The mountains are numbered from 0 to N-1. The contents of the screen are stored in an array of characters pix where pix[x, y] gives the contents of the pixel at column x, row y. Both indices are 0-based. Columns are numbered left to right and rows are numbered bottom to top. The parts of the screen where the i-th mountain is visible are denoted by digit i. Character '.' means that the corresponding pixel is not covered by any mountains.



The i-th (0-based index) mountain is described by its peak position (X[i], Y[i]), 0 <= X[i] < W, 0 <= Y[i] < H. In order to draw the mountains, the following pseudocode is used:



Fill all elements of pix with '.' characters.

For 0 <= i < N:

  For 0 <= x < W:

    For 0 <= y <= Y[i] - |x - X[i]|:

      pix[x, y] := i + '0'



For example, consider three mountains with peaks at (1, 1), (2, 2) and (4, 1). Once these mountains are drawn on a screen with H = 3, W = 6, the resulting picture will look as follows:
..1...
.1112.
111222


Manao has recently filled the background with N mountains as described above. After that he wrote down the height of each mountain. Also, for each column he wrote down which mountains were visible at that column. You are given a int[] heights containing N elements. Element i of heights gives the height of the i-th mountain in pixels (which is equal to Y[i] + 1). You are also given a String[] visibility. It contains N elements and each element is W characters long. The j-th character of visibility[i] is equal to 'X' if the i-th mountain was visible at column j of the screen and '-' otherwise. In other words, the j-th character of visibility[i] is equal 'X' if and only if at least one pixel of column j contained digit i after all mountains were drawn.



Count the number of sequences of exactly N mountains that match the information given by heights and visibility. Return this number modulo 1,000,000,009. It is guaranteed that there exists at least one such sequence.
 

Definition

    
Class:Mountains
Method:countPlacements
Parameters:int[], String[]
Returns:int
Method signature:int countPlacements(int[] heights, String[] visibility)
(be sure your method is public)
    
 

Notes

-The value of H is not directly given in the input parameters. For the purposes of this problem, you can assume that H is equal to the largest element of heights.
 

Constraints

-heights will contain between 1 and 10 elements, inclusive.
-Each element of heights will be between 1 and 50, inclusive.
-visibility will contain the same number of elements as heights.
-Each element of visibility will be between 1 and 50 characters long, inclusive.
-All elements of visibility will be of the same length.
-Each element of visibility will consist of 'X' and '-' characters only.
-At least one sequence of mountains matching the given information will exist.
 

Examples

0)
    
{2, 3, 2}
{"------",
 "XXXX--",
 "---XXX"}
Returns: 4
The given information corresponds to the three mountains from the problem statement. Mountains 1 and 2 are uniquely determined. Mountain 0 can have the peak in each column from 1 to 4.
1)
    
{4, 3, 4}
{"XXXXX--------",
 "----------XXX",
 "----XXXXXXX--"}
Returns: 4
The four possible mountain sequences are:
  • (2, 3), (10, 2), (7, 3)
  • (2, 3), (11, 2), (7, 3)
  • (3, 3), (10, 2), (7, 3)
  • (3, 3), (11, 2), (7, 3)


After drawing these sequences, the following pictures are obtained:

..0....2.....      ..0....2.....      ...0...2.....      ...0...2.....

.000..222.1..      .000..222..1.      ..000.222.1..      ..000.222..1.

000002222211.      0000022222111      .00002222211.      .000022222111

0000222222211      0000222222211      0000222222211      0000222222211

2)
    
{13, 2, 3, 2}
{"XXXXXXXXX",
 "-XXX-----",
 "----XXXXX",
 "-----XXX-"}
Returns: 9
3)
    
{8, 2, 9, 3, 10}
{"X------",
 "-------",
 "------X",
 "-------",
 "XXXXXXX"}
Returns: 98
4)
    
{20, 20, 20, 20, 20, 20, 45, 50, 49, 50}
{"-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "------------XXXXXXX",
 "XXXXXXX------------",
 "XXXXXXXXXXXXXXXXXXX"}
Returns: 973726691

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 567 Round 1 - Division I, Level Three