迷宫（不能重复走格子）

题目描述

给定一个 $n$ 行 $m$ 列的迷宫，. 表示可以通行的空地，# 表示墙壁（不可通行）。

起点固定在左上角格子 $(1,1)$，终点固定在右下角格子 $(n,m)$。每一步可以从当前格子走到上、下、左、右四个相邻的格子（不能走出迷宫，也不能走到墙上）。

要求：一条路径中不能重复经过同一个格子（即路径是简单路径）。

求从起点走到终点的不同路径条数。两条路径只要经过的格子序列不同，就视为不同的路径。

提示：因为不能重复走格子，搜索时需要用一个 vis 数组标记已经走过的格子，回溯时取消标记——这就是“判重剪枝”。

输入格式

第一行两个整数 $n$、$m$，表示迷宫的行数和列数。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，仅由字符 . 和 # 组成，表示迷宫的一行。

输出格式

输出一行一个整数，表示从 $(1,1)$ 到 $(n,m)$ 且不重复经过格子的路径条数。

特别地，当起点与终点是同一个格子（即 $n=m=1$）时，规定答案为 $1$。

样例

样例 1

输入：

3 3
...
.#.
...

输出：

2

解释：只有沿最上面一行再向下，或者沿最左边一列再向右这两种走法。

样例 2

输入：

2 3
..#
##.

输出：

0

解释：起点右侧和下方都被封死，无法到达终点。

样例 3

输入：

3 3
...
...
...

输出：

12

数据范围

• $1 \le n, m \le 6$
• 迷宫中每个字符为 . 或 #
• 保证答案在 32 位整数范围内