分数: 425 点
问题陈述
有一个网格 H \times W 细胞。让 (i, j) 表示位于 i从顶部算起的第行和 j左起第 列。
细胞 (i, j) 为空,如果 S_{i,j} is .,如果是则被阻止 #.
计算从空单元格开始的方法数量并使得 K 移动到相邻的单元格(上、下、左或右),不穿过被阻挡的方块,并且不会多次访问同一单元格。
具体来说,计算长度为的序列的数量 K+1, ((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K)),满足以下条件。
- 1 \leq i_k \leq H, 1 \leq j_k \leq W,和 S_{i_k, j_k} is
.,对于每个 0 \leq k \leq K. - |i_{k+1} - i_k| + |j_{k+1} - j_k| = 1 对于每个 0 \leq k \leq K-1.
- (i_k, j_k) \neq (i_l, j_l) 对于每个 0 \leq k < l \leq K.
约束
- 1 \leq H, W \leq 10
- 1 \leq K \leq 11
- H, W,和 K 是整数。
- 每个 S_{i,j} is
.or#. - 至少有一个空单元格。
输入
输入由标准输入按以下格式给出:
H W K
S_{1,1}S_{1,2}\dots S_{1,W}
S_{2,1}S_{2,2}\dots S_{2,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}
输出
打印答案。
示例输入 1
2 2 2 .# ..
示例输出 1
2
以下是两个可能的路径:
- (1,1) \rightarrow (2,1) \rightarrow (2,2)
- (2,2) \rightarrow (2,1) \rightarrow (1,1)
示例输入 2
2 3 1 .#. #.#
示例输出 2
0
示例输入 3
10 10 11 ....#..#.. .#.....##. ..#...##.. ...#...... ......##.. ..#......# #........# ..##...... .###....#. ...#.....#
示例输出 3
218070