题目背景

你醒来时发现自己被困在一间密室里，面前是一张地图。 你必须找到所有可能的逃生路线——出口可能不止一条路能到。

题目描述

密室是一个 $n \times m$ 的网格，每个格子是以下三种之一：

• S：你的起始位置
• E：出口位置
• #：墙壁（不可通过）
• .：空地（可以通过）

你每次可以向上、下、左、右四个方向移动一格，且不能重复经过同一个格子。 请统计从起点到出口一共有多少条不同的路径。

如果无法到达出口，输出 $0$。

输入格式

第一行两个正整数 $n$ 和 $m$，表示密室的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符，描述密室地图。 保证有且仅有一个起点 S 和一个出口 E。

输出格式

输出一个整数，表示从起点到出口的不同路径总数。

样例输入

3 3
S..
...
..E

样例输出

12

样例解释

$3 \times 3$ 网格，起点 $(1,1)$，出口 $(3,3)$，无墙壁，共有 $12$ 条不同路径。

注意：路径可以绕路，只要不重复经过同一格子即可。

数据范围与约定

对于 $100\%$ 的数据，$2 \le n, m \le 5$。

提示

• 用深度优先搜索（DFS）+ 回溯法：从起点出发，尝试四个方向，标记已访问，递归搜索，回溯时取消标记。
• 搜索时需要判断边界条件（不出界、不是墙、没走过）。
• 不需要使用 std::vector，直接开固定大小的二维数组即可（最大 $5 \times 5$）。