Connection Status:
Competition Arena > MagicalGirlLevelTwoDivOne

MagicalGirlLevelTwoDivOne

SRM 514 · 2011-05-25 · by wrong

SRM 514 · 2011-05-25 · by wrong · Dynamic Programming
Class Name: MagicalGirlLevelTwoDivOne
Return Type: int
Method Name: theCount
Arg Types: (vector<string>, int, int)
Problem Statement

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 String[] 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.

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

Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MagicalGirlLevelTwoDivOne with a public method int theCount(vector<string> palette, int n, int m) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous