小慕正在开发一个迷宫探索游戏，其中有一个核心关卡需要完成：玩家需要从指定的起点出发，找到藏在迷宫深处的宝藏，并且必须经过地图上所有可通行的空地恰好一次，最终抵达宝藏所在的位置。 迷宫的地图用一个 `grid` 表示，每个格子代表不同的地形： - 数字 `1` 表示玩家的起点。 - 数字 `2` 表示宝藏所在的终点。 - 数字 `0` 表示可以通行的空地。 - 数字 `-1` 表示，无法通行。 在游戏中，玩家只能朝上、下、左、右四个方向移动，且不能重复经过任何一块空地。小慕需要计算从起点到终点所有可能的路径数量，其中每条路径都必须经过每一块可以通行的空地。
提示：带虚线的词点一下有通俗解释。
输入描述
输入的第一行包含两个整数 `m` 和 `n`，表示网格的行数和列数 `(1 <= m * n <= 20)`。 接下来的 `m` 行中，每行包含 `n` 个整数，表示房间的布局。每个整数的值可以是以下之一： - `1`：表示起点。 - `2`：表示终点。 - `0`：表示可以通行的空地。 - `-1`：表示障碍物。
输出描述
输出一个整数，表示从起点到终点的所有不同路径数目。如果不存在路径，输出 `0`。
示例
示例 1
输入
3 4 1 0 0 0 0 0 0 0 0 0 2 -1
输出
2
说明：有以下两条路径： 1. `(0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (1,1) -> (1,0) -> (2,0) -> (2,1) -> (2,2)` 2. `(0,0) -> (1,0) -> (2,0) -> (2,1) -> (1,1) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (2,2)`
示例 2
输入
3 4 1 0 0 0 0 0 0 0 0 0 0 2
输出
4
说明：有以下四条路径： 1. `(0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (1,1) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (2,3)` 2. `(0,0) -> (0,1) -> (1,1) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (1,2) -> (0,2) -> (0,3) -> (1,3) -> (2,3)` 3. `(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (1,2) -> (1,1) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (2,3)` 4. `(0,0) -> (1,0) -> (2,0) -> (2,1) -> (1,1) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (1,2) -> (2,2) -> (2,3)`
示例 3
输入
2 2 0 1 2 0
输出
0
说明：没有一条路径能完全穿过每一个空的方格一次。
时间限制 1000 ms · 内存限制 128 MB