P5146: 动物园里有什么

---

【题目描述】

题目描述

动物园里有什么？大老虎、大狮子、大灰狼…… 当这三种猛兽真的在动物园里相遇，就给园长出了个不小的难题。
具体来说，动物园里有一片 N行 M列的方格形场地，每格的状态可用字符 'X'或 '?'表示。'X'表示该格没有笼子，因此不能饲养猛兽；'?' 表示该格有笼子，可以饲养任意一只猛兽。
可供饲养的三种猛兽中，老虎是独居动物，不能与任何动物相邻；狼和狮子是群居动物，它们都只能与同类相邻。（如果任意两格有共同边，我们就称这两格相邻。）
糟糕的是，未来 T个月内，每个月都会有一只笼子损毁。也就是说，该笼子此前一直处于正常使用状态，但从该月起永久失效。数据保证，每个月都至少有一个可供使用的笼子，即不会所有笼子均失效。
园长想知道，要将场地内所有可供使用的笼子放满猛兽，每个月分别有多少种排布方案。（答案需对10⁹+7取模。）

输入描述

第 1 行为 3 个整数 N, M, T，表示场地有 N行 M列，要经过 T个月。
接下来 N行，每行 M个字符，均为 'X'或 '?'，表示每格的状态。
接下来 T 行，每行两个整数 R, C，表示第 R行第 C列的笼子将从该月起失效，不能再存放猛兽。

输出描述

共 T+1行，每行一个整数，为该月的可行排布方案数，答案需对 10⁹+7取模。

样例1

输入
3 4 2
?XX?
X??X
??X?
1 4 2 2
输出
54
18
54

样例2

输入
3 3 5
???
???
???
2 2
2 1
2 3
1 2
3 2
输出
2
2
2
4
18
81

提示

对于 20% 的数据，N = 1, T = 0;
对于 40% 的数据，0 < N, M≤100, T = 0;
对于 60% 的数据，0 < N, M≤100,,0≤T≤100;
对于 80% 的数据，0 < N, M≤1000, 0≤T≤1000;
对于 100% 的数据，0 < N, M≤1000, 0≤T≤10⁵.

【输入】

第 1 行为 3 个整数 N, M, T，表示场地有 N行 M列，要经过 T个月。

接下来 N行，每行 M个字符，均为 'X'或 '?'，表示每格的状态。

接下来 T 行，每行两个整数 R, C，表示第 R行第 C列的笼子将从该月起失效，不能再存放猛兽。

【输出】

共 T+1行，每行一个整数，为该月的可行排布方案数，答案需对 10⁹+7取模。

【提示】

对于 20% 的数据，N = 1, T = 0;

对于 40% 的数据，0 < N, M≤100, T = 0;

对于 60% 的数据，0 < N, M≤100,,0≤T≤100;

对于 80% 的数据，0 < N, M≤1000, 0≤T≤1000;

对于 100% 的数据，0 < N, M≤1000, 0≤T≤10⁵.

题目类型~

海淀区第五届“智慧杯”中小学生计算机程序设计大赛普及组 

咻咻~

提交答案 状态 返回