A1002.Balanced Subsets--Platinum
省选/NOI-
USACO
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
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≤i≤N, 1≤j≤N (1≤N≤150). 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 (x1,y) and (x2,y) (x1≤x2) are part of the subset, then all cells (x,y) with x1≤x≤x2 are also part of the subset.
- If cells (x,y1) and (x,y2) (y1≤y2) are part of the subset, then all cells (x,y) with y1≤y≤y2 are also part of the subset.
Count the number of balanced subsets modulo 109+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 109+7.
输入输出样例
输入#1
2 GG GG
输出#1
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