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)(i,j) for each
1iN1\le i\le N, 1jN1\le j\le N (1N1501\le N\le 150). Some of the cells contain
grass.
A nonempty subset of grid cells is called "balanced" if the following
conditions hold:

  1. All cells in the subset contain grass.
  2. 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.
  3. If cells (x1,y)(x_1,y) and (x2,y)(x_2,y) (x1x2x_1\le x_2) are part of the subset, then all cells (x,y)(x,y) with x1xx2x_1\le x\le x_2 are also part of the subset.
  4. If cells (x,y1)(x,y_1) and (x,y2)(x,y_2) (y1y2y_1\le y_2) are part of the subset, then all cells (x,y)(x,y) with y1yy2y_1\le y\le y_2 are also part of the subset.
    Count the number of balanced subsets modulo 109+710^9+7.

输入格式

The first line contains NN.
The next NN lines each contain a string of NN characters. The jj-th
character of the ii-th line from the top is equal to G if the cell at (i,j)(i,j)
contains grass, or . otherwise.

输出格式

The number of balanced subsets modulo 109+710^9+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

首页