分数: 300 点
问题陈述
我们有一个网格 H 行和 W 方格列。正方形的颜色 i从顶部开始的第行和 j左起第 列 (1 \leq i \leq H, 1 \leq j \leq W) 作为一个角色给予你 c_{i,j}:如果满足以下条件,则方块为白色: c_{i,j} is .,如果 c_{i,j} is #.
考虑执行以下操作:
- 选择一定数量的行(可能为零)和一定数量的列(可能为零)。然后,将所选行中的所有方块和所选列中的所有方块涂成红色。
给你一个正整数 K。有多少行和列的选择会产生准确的结果 K 操作后还剩下黑色方块吗?在这里,当仅在其中一个选项中选择了行或列时,我们认为两个选项是不同的。
约束
- 1 \leq H, W \leq 6
- 1 \leq K \leq HW
- c_{i,j} is
.or#.
输入
输入由标准输入按以下格式给出:
H W K
c_{1,1}c_{1,2}...c_{1,W}
c_{2,1}c_{2,2}...c_{2,W}
:
c_{H,1}c_{H,2}...c_{H,W}
输出
打印一个整数,表示满足条件的行和列的选择数。
示例输入 1
2 3 2 ..# ###
示例输出 1
5
以下五个选项满足条件。
- 的 树的 1-st 行和 1-st 列
- 的 树的 1-st 行和 2-nd 列
- 的 树的 1-st 行和 3-rd 列
- 的 树的 1-st 和 2-nd 列
- 的 树的 3-rd 列
示例输入 2
2 3 4 ..# ###
示例输出 2
1
一种选择(即不选择任何内容)满足条件。
示例输入 3
2 2 3 ## ##
示例输出 3
0
示例输入 4
6 6 8 ..##.. .#..#. #....# ###### #....# #....#
示例输出 4
208