GravityPuzzle
SRM 724 · 2017-11-27 · by cgy4ever
SRM 724 · 2017-11-27 · by cgy4ever · Math
Problem Statement
Problem Statement
Gravity Puzzle is a game played on a rectangular board divided into unit square cells.
Each cell contains at most one box.
There are four buttons, labeled Left, Right, Up, and Down. You play the game by pushing these buttons (one at a time, in any order, each button arbitrarily many times).
At the beginning of the game, there is no gravity, so each box remains in its cell. The buttons control gravity: pushing a button turns on gravity in the direction given on its label. Gravity makes all the boxes fall in the given direction: whenever the cell next to a box in the given direction is empty, the box moves into that cell. Note that each time you push a button, all boxes immediately fall as far as they can in the given direction of gravity.
For example, if you push the button labeled Down, all boxes will immediately fall downwards until no more movement is possible. Thus, after you push the button labeled Down, within each column the boxes will move to the bottommost rows.
Below are two examples that show the effect of pushing the buttons labeled Down and Right from the same configuration of boxes. Boxes are denoted '#' and empty cells '.'.
You are given one particular configuration of boxes on the board in theString[] board.
The elements of board describe the rows of the board from top to bottom.
(I.e., board[0] describes the topmost row of the board, and so on.)
The characters of board[r] describe the cells in row r from left to right, with '.' being an empty cell and '#' a cell with a box.
The configuration of boxes given in board is the desired final configuration. A starting configuration C of boxes is winnable if there is a sequence of zero or more button presses that changes C into the configuration given in board.
If the board has r rows and c columns, there are 2^(r*c) possible starting configurations of boxes, because each of the r*c cells is either empty or it contains a box. Please count how many of these configurations are winnable, and return that count modulo 10^9 + 7.
There are four buttons, labeled Left, Right, Up, and Down. You play the game by pushing these buttons (one at a time, in any order, each button arbitrarily many times).
At the beginning of the game, there is no gravity, so each box remains in its cell. The buttons control gravity: pushing a button turns on gravity in the direction given on its label. Gravity makes all the boxes fall in the given direction: whenever the cell next to a box in the given direction is empty, the box moves into that cell. Note that each time you push a button, all boxes immediately fall as far as they can in the given direction of gravity.
For example, if you push the button labeled Down, all boxes will immediately fall downwards until no more movement is possible. Thus, after you push the button labeled Down, within each column the boxes will move to the bottommost rows.
Below are two examples that show the effect of pushing the buttons labeled Down and Right from the same configuration of boxes. Boxes are denoted '#' and empty cells '.'.
...# .... .##. 'Down' -> .#.. .#.. .### ...# ...# .##. 'Right' -> ..## .#.. ...#
You are given one particular configuration of boxes on the board in the
The configuration of boxes given in board is the desired final configuration. A starting configuration C of boxes is winnable if there is a sequence of zero or more button presses that changes C into the configuration given in board.
If the board has r rows and c columns, there are 2^(r*c) possible starting configurations of boxes, because each of the r*c cells is either empty or it contains a box. Please count how many of these configurations are winnable, and return that count modulo 10^9 + 7.
Constraints
- board will contain between 1 and 50 elements, inclusive.
- Each element in board will contain between 1 and 50 characters, inclusive.
- Each element in board will contain the same number of characters.
- Each character in board will be '.' or '#'.
Examples
0)
{"#...",
"....",
"...."}
Returns: 12
The winnable configurations are precisely the 12 configurations that contain exactly one box: you can push 'Left' then push 'Top' and that box will be in the top-left corner.
1)
{".#."}
Returns: 1
This time we only have one solution: {".#."} itself.
2)
{"#.",
"##"}
Returns: 4
We have these 4 solutions: #. ## {} ## .# {"Down", "Left"} .# ## {"Left"} ## #. {"Down"}
3)
{".##",
"..#",
"..."}
Returns: 72
4)
{".##########.",
"............",
"............",
"............",
"............",
"............",
"............",
"............",
"............",
"............"}
Returns: 999999937
Don't forget mod.
Submissions are judged against all 99 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class GravityPuzzle with a public method int count(vector<string> board) · 99 test cases · 2 s / 256 MB per case