← 返回题目列表

AtCoder · abc378_d

G. 计算简单路径

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

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