시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 32 | 20 | 19 | 63.333% |
Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chessboard) labeled by the ordered pairs $(i,j)$ for each $1\le i\le N$, $1\le j\le N$ ($1\le N\le 150$). Some of the cells contain grass.
A nonempty subset of grid cells is called "balanced" if the following conditions hold:
Count the number of balanced subsets modulo $10^9+7$.
The first line contains $N$.
The next $N$ lines each contain a string of $N$ characters. The $j$-th character of the $i$-th line from the top is equal to G if the cell at $(i,j)$ contains grass, or . otherwise.
The number of balanced subsets modulo $10^9+7$.
2 GG GG
13
For this test case, all 4-connected subsets are balanced.
G. .G .. .. GG .G .. G. GG .G G. GG GG .., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG
4 GGGG GGGG GG.G GGGG
642
Here is an example of a subset that satisfies the second condition (it is 4-connected) but does not satisfy the third condition:
GG.. .G.. GG.. ....