障碍物迷宫

题目描述

有一个 $n \times m$ 的迷宫。

迷宫中包含三种字符：

S 表示起点
E 表示终点
. 表示可以经过的空地
# 表示墙壁，不能经过

小明从起点 S 出发，想走到终点 E。

每一步可以向四个方向移动：

上、下、左、右

但是有两个限制：

不能走出迷宫
不能走到墙壁 #
同一个格子不能重复经过

请你计算从 S 到 E 一共有多少条不同路径。

输入格式

第一行输入两个整数 $n,m$。

接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，表示迷宫地图。

输出格式

输出一个整数，表示从 S 到 E 的不同路径数量。

数据范围

1 ≤ n,m ≤ 6

保证地图中恰好有一个 S 和一个 E。

样例输入 1

3 3
S..
.#.
..E

样例输出 1

2

样例解释 1

可以绕过中间的墙壁，共有 2 条路径。

样例输入 2

3 3
S#.
.#.
..E

样例输出 2

0

样例解释 2

起点附近被墙壁阻挡，无法到达终点。

题解

本题是典型的 DFS 回溯题。

核心思想是：

从当前位置出发
尝试四个方向
能走就进入
走完之后回溯

这就是回溯。

训练点总结

1. DFS 搜索
2. 四方向移动
3. 障碍物判断
4. vis 防止重复访问
5. 回溯恢复现场