USACO 2021 US Open, Platinum
Problem 3. Balanced Subsets
Contest has ended.
Log in to allow submissions in analysis mode
Farmer John 的草地可以被看作是由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘），对于每一个 1≤i≤N、1≤j≤N，方格可以用有序对 (i,j) 表示（1≤N≤150）。某些方格中含有草。
Contest has ended. No further submissions allowed.
方格的一个非空子集被称为是「平衡的」，如果以下条件成立：
- 所有子集中的方格均含有草。
- 子集是四连通的。换句话说，从子集中的任一方格到另一方格均存在一条路径使得路径中的相邻方格均水平或竖直方向上相邻。
- 如果方格 (x1,y) 和 (x2,y)（x1≤x2）存在于子集中，那么所有满足 x1≤x≤x2 的方格 (x,y) 也存在于子集中。
- 如果方格 (x,y1) 和 (x,y2)（y1≤y2）存在于子集中，那么所有满足 y1≤y≤y2 的方格 (x,y) 也存在于子集中。
计算平衡的子集数量模 109+7 的结果。
输入格式（从终端 / 标准输入读入）：
输入的第一行包含 N。以下 N 行每行包含一个长为 N 的字符串。如果方格 (i,j) 中有草，则第 i 行的第 j 个字符为 G，否则为.。
输出格式（输出至终端 / 标准输出）：
输出平衡的子集数量模 109+7 的结果。输入样例：
2 GG GG
输出样例：
13
对于这个测试用例，所有的四连通子集均是平衡的。
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
以下是一个符合第二个条件（四连通）但不符合第三个条件的子集的例子：
GG.. .G.. GG.. ....
测试点性质：
- 测试点 1-4 满足 N≤4。
- 测试点 5-10 满足 N≤20。
- 测试点 11-20 没有额外限制。
供题：Benjamin Qi