14049 - 走迷宫 Ⅷ

有一个 n 行 m 列的二维网格，从起点 (s_i, s_j) 出发，需要走到终点 (e_i, e_j)。每次移动可以向上、下、左、右四个方向移动到相邻的网格，但不能重复经过已经走过的网格（即路径不能有环）。网格中有一些障碍物（用 # 表示），不能通过。请你计算从起点到终点的所有不同移动方案总数。

第一行包含六个整数 n, m, s_i, s_j, e_i, e_j ，用空格隔开：

• n ：网格的行数
• m ：网格的列数
• s_i, s_j ：起点的行号和列号（从 1 开始编号）
• e_i, e_j ：终点的行号和列号

接下来 n 行，每行包含一个长度为 m 的字符串，由字符 . 和 # 组成：

• . 表示可通行的网格
• # 表示障碍物，不能进入

保证起点和终点均为 .。

输出一个整数，表示从起点到终点的不同路径总数（路径不允许重复经过同一网格）。如果无法到达，输出 0。

样例说明

网格为 4 行 4 列：

行1: . . .

行2: . # . # .

行3: . # . # .

行4: . . .

起点 (1,1)，终点 (4,4)。从起点到终点不经过重复格子的路径有两条（具体路径略），因此输出 2。

数据范围与约定

• 1 \le n, m \le 9
• 起点和终点坐标合法，且均为可通行格。