Newgenerations
TCO19 SRM 756 · 2019-04-24 · by IH19980412
Problem Statement
Uzuki, Rin and Mio are friends. Today they are going to create a game!
The field of the game is a rectangular grid of cells. You are given its map in the
- 'x' is a special cell (explained below)
- '#' is an active cell
- '.' is an inactive cell
- '*' is an undecided cell that can become either active or inactive
There are at most 20 special cells. Each special cell is an active cell.
The following sequence of events is about to happen:
- The friends will decide which of the undecided cells will become active and which ones will become inactive.
- Each pair of adjacent active cells will be connected by a pipe. (Two cells are adjacent if they share a side.)
- Uzuki will paint some pipes red, Rin will paint some other pipes blue, and Mio will paint all the remaining pipes yellow.
They have to be careful when painting the pipes. Research has shown that players of the game become confused if two pipes of the same color are connected to the same special cell. (Note that other active cells may be incident to multiple pipes of the same color.)
A way of changing the '*' cells into '#' and '.' cells is called valid if it is then possible to paint all pipes without confusing the players.
Return the number of valid ways to resolve the undecided cells, modulo 1,000,000,007.
Constraints
- N will be between 1 and 50, inclusive.
- M will be between 1 and 50, inclusive.
- field will contain exactly N elements.
- Each element in field will contain exactly M characters.
- Each character in field will be 'x' or '#' or '.' or '*'.
- field will contain between 0 and 20 'x's, inclusive.
{"x*"
,"*#"}
Returns: 4
There are four possible assignments: x# x# x. x. ## .# ## .# In the first case, all cells are now active, so there will be four pipes. In the second and third case, three cells are active and thus two pipes will appear. In the fourth case, two cells are active, but no pipes will appear because the active cells are not adjacent. In all cases, the authors can paint every pipe in one of three colors so that players will never get confused. (For example, in the first case they can paint both horizontal pipes red and both vertical ones blue.
{"##."
,".#."
,".##"}
Returns: 1
Five cells are active and four pipes will appear between them. As there are no undecided cells, there is exactly one way to resolve the undecided cells: do nothing. As there are no special cells, any coloring of pipes is OK, which means that the one way mentioned in the previous paragraph is a valid solution.
{"#.......#.......#"
,"##.....###.....##"
,"###...#####...###"
,"####.x#####x.####"
,"####xxx###xxx####"
,"###xx*******xx###"
,"##x***********x##"
,"#***************#"}
Returns: 134217728
{"#****#*#*****#******"
,"#****#..*.#*#*.*x.#*"
,"****#**#**##*****#**"
,"*##***#*##x*x***#x*x"
,"****#*#*****#*****#*"
,".**###*#**x*.*###**x"
,"*#**##*.**#****x**.*"
,"#************.***#**"
,"*******#*#****#***.*"
,"*#.***##**.**##.#*##"
,"*.##****.****#.****x"
,"*.*#****#*##*#***.#*"
,"###x#*.***#x***#***#"
,"#*.**#**#*******#.**"
,"****#x***##x*.##.*#*"
,"*###*###****.**#****"
,"*.*#*****###****##**"
,"*#*#**.*#*x*##**#***"
,"*##*******#x#**#****"
,"***##*******#*******"}
Returns: 961436185
{"*#.*****#.#******#**##..*##.***.#*##x##.*#.**###**","*.****#**#***#*****##**##*******####***##*********","***.****#**##..**#*******#*#*****#.**##.**#****.*#","##**.*****.**##**.***#**.##****##**.*#**#*#*.*****","*#.#***#*****#*****.*#.#******.###****.#******..#*","****.*#.*.*********.***#***#..#***###***#**#*###*#","#.****#**.*#****#*###**#*..*..##.#*****.#*#*##*#**","***#.*#.**.***#.************.*****#***#**#****#.#.","#**#********#***#**..**#.#.**..*******#**#**##**#*","******x*#****###****#**.#*##*************#*.#*..#*","*##****.***.***#*##..###*******.******#*x**.***..*","**#*##**#*#*#.##.*.*####*.*###*#*...*###***#.#.#**","#*********#*#*#****.**.*******.**.#.********#***.*","#x***#***.#*.*.***********..*x******#*#*#****.**.#","***#*#******#*#***##****#**#**.****#.**.*#****#***","###**********#*******.******.#****#*.#***###*#*..*","****#*******##**#****#****.*#****.#***#*#.*.**##**","*##*.**##*###x*.***.**#*#*x****#****#.*#**.*#.**.*","*#**..***####***.*#***.#*.*.#*#.*#***#.*#*#.**.*##","##***#**#.#.#*#**.*#**##*********#.**##*#**.***#**",".**#*.**.**.#***.********#*.****.****#***.*##*#**x","****x**.*#**.***x#**#****..#..*#***#**#*******.**#",".**###*****#**##***.#*****#*****#**...*#***.****x*","#####.***.**##*#**#**.*#*****#**###**#.##********x","#*.*.#**###*#*#**.***#*..*.*.#**#*.**#.*#*.#*.***#","**#*.*#*****#*******.***.****.****#*#..**.*####*##","**#**##****#******.#****#**##*.#*##*.*#****#***#.#","#*.*.***.*.*#*#.***.*#*#x#******###.**#*.#*##****#","***.#**..*###***..*******#*.*.**#**##**.**##.**#**","***##***##.**##***#*##*.#.#**##***#**#*******#*#**","*#*****#****#*##*.***.#*#**#**#*#*#**#.**.******#*","*****#***.#*#***.*##.#***#****#*###*#**********#*#","*****##*******#.##***.##**#*#***#****##****###*##.","*##*.#*x##***#*#******#**#****.#*.##*#*#.*#****.##","**********.*****.##*#*##**#**#*****#.#**.#.****.**","***###..#**#*#.**.**##**#*#**.***.**#****#*.******","***##**x...*#*****.*#***#**#*******.**..#*##******",".*#**#.****...*##..*.##.*#****##**#.##*.****..***.","****.*#x*#*.#***.*#*****#.***..*##*#.*.#**#**####*","*.*#**#**x***.****#*#*#***.#*#**#.**.#***#*#.**#.*","#*##***.**.*###.#****.#**.**##.*#.****#**.#.**#***","#*##********#****..#*#*****.**#.##**#.***#***##*.*",".#.x*.#***#*#.#**.*****.****.*#*#*.##**#**#*****#*","*#.**#*.*#*###*#*.****#***.*.#*..***#**.##******#*","#*##*###*##.##****.*#*##*******#.*#*..***##***#***","**##*.*******#*.***#*.*******#*#.*#*#..#**.*#***#*","#*.****.***************x***##**##***#.**#.#*#*#*.*","#********#***#*****#******#.x**.*****.*..*#***#**.","**#*#*#**#*##****#***.*****#****#.*.******.#**##**","***#**#.*.*.#**##******##*#*******##.#*#***#.#***#"}
Returns: 340808914
Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Newgenerations with a public method int count(vector<string> field) · 84 test cases · 2 s / 256 MB per case