PROBLEM STATEMENT
Magical Girls are girls who have magical powers. They fight against evil witches to protect the
Earth.
You, one of the Magical Girls, found a slate palette. You know that the information of an ancient
magic is written on the palette. Unfortunately, some parts of the palette are broken, so you
cannot read all the information.
The information is indicated by a rectangular grid whose width is W and height is H. Rows are
numbered from 0 to H-1 from top to bottom. Columns are numbered from 0 to W-1 from left to right.
Each cell of the grid should contain an integer between 1 and 9, inclusive. Now some of the cells
are broken and don't contain a digit. You want to know how many ways the empty cells can be filled
so that the completed grid meets the following conditions:
For all integers r and c, where 0 <= r <= H-n and 0 <= c < W, the sum F[r][c] + F[r+1][c] + ... +
F[r+n-1][c] must be an odd number. (Here F[r][c] is a number written in the cell whose row number
is r and column number is c.)
For all integers r and c, where 0 <= r < H and 0 <= c <= W-m, the sum F[r][c] + F[r][c+1] + ... +
F[r][c+m-1] must be an odd number.
You are given a vector palette. The j-th character of the i-th element of palette is a
digit ('1'-'9') if the cell (i, j) is not broken, or a dot ('.') if the cell (i, j) is broken and
now empty. Return the number of ways to fill the grid modulo 1,000,000,007.
DEFINITION
Class:MagicalGirlLevelTwoDivOne
Method:theCount
Parameters:vector , int, int
Returns:int
Method signature:int theCount(vector palette, int n, int m)
CONSTRAINTS
-palette will contain between 1 and 50 elements, inclusive.
-Each element of palette will contain between 1 and 50 characters, inclusive.
-Each element of palette will contain the same number of characters.
-Each character in palette will be '1', '2', '3', '4', '5', '6', '7', '8', '9', or '.'.
-n will be between 1 and min{10, H}, inclusive, where H is the number of elements in palette.
-m will be between 1 and min{10, W}, inclusive, where W is the number of characters in palette[0].
EXAMPLES
0)
{"12",
"2."}
2
2
Returns: 5
The?missing?digit?can?be?filled?with?'1',?'3',?'5',?'7'?or?'9'.
1)
{"21",
"1."}
2
2
Returns: 4
This?time?it?can?be?filled?with?'2',?'4',?'6'?or?'8'.
2)
{"...",
"...",
"..."}
1
1
Returns: 1953125
3)
{"..58..",
"..47.."}
2
3
Returns: 0
It's impossible to fill this grid.
4)
{"...1.2.3",
"4.5.6...",
"...7.8.9",
"1.2.3..."}
4
4
Returns: 886073030
5)
{"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"...................."}
10
10
Returns: 240076532
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.