Balanced Subsets
Time limit1sMemory limit512 MB
Count connected subsets of grass cells in an N by N grid where every row and column intersects the subset in a single contiguous run, modulo 1e9+7.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Implementation, Matrix, Combinatorics
- Solved
- No attempts yet
Problem
Farmer John's pasture can be regarded as a large 2D grid of square cells (picture a huge chessboard) labeled by the ordered pairs for each , (). Some of the cells contain grass.
A nonempty subset of grid cells is called "balanced" if the following conditions hold:
- All cells in the subset contain grass.
- The subset is 4-connected. In other words, there exists a path from any cell in the subset to any other cell in the subset such that every two consecutive cells of the path are horizontally or vertically adjacent.
- If cells and () are part of the subset, then all cells with are also part of the subset.
- If cells and () are part of the subset, then all cells with are also part of the subset.
Count the number of balanced subsets modulo .
Input
The first line contains .
The next lines each contain a string of characters. The -th character of the -th line from the top is equal to G if the cell at contains grass, or . otherwise.
Output
Print the number of balanced subsets modulo .