H and V

题目描述

我们有一个由 $H$ 行 $W$ 列方格组成的网格。位于从上数第 $i$ 行、从左数第 $j$ 列的方格的颜色由字符 $c_{i,j}$ 给出：若 $c_{i,j}$ 是 $.$ 则该方格为白色，若 $c_{i,j}$ 是 # 则该方格为黑色。考虑执行以下操作：

选择若干行（可以为零），以及若干列（可以为零）。然后，把所有被选中的行中的方格和所有被选中的列中的方格涂成红色。

给定一个正整数 $K$ 。有多少种行和列的选择能使得操作后恰好剩下 $K$ 个黑色方格？在这里，当某一行或某一列只在其中一个选择中被选中时，我们认为这两个选择不同。

输入从标准输入按如下格式给出： $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}$

输出一个整数，表示满足条件的行和列选择数。

2 3 2
..#
###

2 3 4
..#
###

2 2 3
##
##

6 6 8
..##..
.#..#.
#....#
######
#....#
#....#

$1 \leq H, W \leq 6$ $1 \leq K \leq HW$ $c_{i,j}$ 是 $.$ 或 #。下面五种选择满足条件。

第 $1$ 行和第 $1$ 列第 $1$ 行和第 $2$ 列第 $1$ 行和第 $3$ 列第 $1$ 行和第 $2$ 列第 $3$ 列
还有一种选择，即什么都不选，也满足条件。

标签: AtCoder|abc173C

AtCoder|abc173C