14046 - 迷宫问题

有一个 N \times N 的方格迷宫（ 2 \le N \le 10 ），入口位于左上角 (1,1)，出口位于右上角 (1,N)。
迷宫中的每个格子要么是 0（可通行），要么是 1（障碍物，不可通行）。保证入口和出口处一定是 0。

从某个格子出发，可以朝 八个方向（上、下、左、右、左上、右上、左下、右下）移动一步，但只能移动到迷宫范围内且数字为 0 的格子。
移动过程中不能重复经过同一个格子。

请找出所有从入口到出口的路径总数，如果无法到达，则输出 0。

第一行包含一个整数 N ，表示迷宫的大小。
接下来 N 行，每行包含 N 个整数（0 或 1），表示迷宫的布局。

输出一个整数，表示从入口到出口的路径总数。

样例说明

迷宫为：

0 0 0

0 1 1

1 0 0

入口 (1,1)，出口 (1,3)。 可行的两条路径为：

1. (1,1) → (1,2) → (1,3)
2. (1,1) → (2,1) → (3,1) → (3,2) → (2,2) → (1,2) → (1,3) （注意不能重复经过格子）

所以输出 2。

数据范围与约定

• 2 \le N \le 10
• 迷宫中的数字仅为 0 或 1。

一本通