Sprinklers 2: Return of the Alfalfa

提交数: 1, 通过率: 100%, 平均分: 100

题目描述:

Farmer John 有一块小的田地，形状为一个 N 行 N 列的一个方阵（1≤N≤2000），对于所有的1≤i,j≤N，从上往下的第 i 行的从左往右第 j 个方格记为(i,j)。他有兴趣在他的田地里种植甜玉米和苜蓿。为此，他需要安装一些特殊的洒水器。

在方格 (I,J) 中的甜玉米洒水器可以喷洒到所有左下方的方格：即满足 I≤iI≤i 以及 j≤Jj≤J 的 (i,j)。

在方格 (I,J) 中的苜蓿洒水器可以喷洒到所有右上方的方格：即满足 i≤Ii≤I 以及 J≤jJ≤j 的 (i,j)。

被一个或多个甜玉米洒水器喷洒到的方格可以长出甜玉米；被一个或多个苜蓿洒水器喷洒到的方格可以长出苜蓿。但是被两种洒水器均喷洒到（或均喷洒不到）的方格什么也长不出来。

帮助 FJ 求出在他的田地里安装洒水器的方法数（模 109+7），每个方格至多安装一个洒水器，使得每个方格均能生长作物（即被恰好一种洒水器喷洒到）。

某些方格正被长毛奶牛占据；这不会阻止这些方格生长作物，但是这些方格里不能安装洒水器。

输入格式:

输入的第一行包含一个整数 N。

对于每一个 1≤i≤N，第 i+1 行包含一个长为 N 的字符串，表示方阵的第i 行。字符串中的每个字符为 'W'（表示被一头长毛奶牛占据的方格）或 '.'（未被占据）。

输出格式:

输出安装洒水器的方法数除以 109+7 的余数。

样例输入:

样例1
2
..
..

样例2
4
..W.
..WW
WW..
...W

样例输出:

样例1
28

样例2
2304

提示:

这个样例符合第一个子任务的限制。

测试点性质：
  • 测试点 3-4 满足 N≤10 并且至多只有十个未被占据的方格。
  • 测试点 5-9 满足 N≤200。
  • 测试点 10-16 没有额外限制。
时间限制: 1000ms
空间限制: 256MB

来源: USACO 2020 OPEN Platinum