原题链接

点我进入原题提交页面

题目描述

给定一个 $H$ 行 $W$ 列的网格；令 $(i, j)$ 为网格中从上到下第 $i$ 行、从左到右第 $j$ 列的格子。

当 $S_{i,j}$ 为 . 时，格子为空格；当 $S_{i,j}$ 为 # 时，格子为障碍物。

请计算从某个空格出发，经过 $K$ 次移动（上下左右），不经过障碍物且不重复经过同一个格子的路径数。

输入格式

第一行输入 $H$ $W$ $K$

接下来输入一个 $H\times W$ 的字符矩阵。

输出格式

输出一个整数代表答案。

2 2 2
.#
..

2

2 3 1
.#.
#.#

0

10 10 11
....#..#..
.#.....##.
..#...##..
...#......
......##..
..#......#
#........#
..##......
.###....#.
...#.....#

218070

提示

数据范围

• $1 \leq H, W \leq 10$
• $1 \leq K \leq 11$
• $H$, $W$, 和 $K$ 均为整数。
• 每个 $S_{i,j}$ 均为 . 或 #。
• 网格中至少存在一个格子为空格。

样例 1 解释

有两种路径分别如下

• $(1,1)\ \to\ (2,1)\ \to\ (2,2)$
• $(2,2)\ \to\ (2,1)\ \to\ (1,1)$