← 返回题目列表

AtCoder · abc173_c

C. H 和 V

中文机器翻译题面 查看原题

分数: 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