八个方向统计线路

题目描述

已知山洞里面是由许多房间组成的迷宫，每个房间可以通往周围八个房间，迷宫大小是一个 $N \times N$ 的正方形，其中有一些蝙蝠堵路。现在从起始 $(1,1)$ 的位置进入洞穴寻找宝藏（只有一个宝箱），统计有多少条线路可以找到宝藏（每条线路经过的格子只能访问 $1$ 次）。

注意：每个房间可以通往周围八个房间（上、下、左、右、四个对角线方向）。

输入格式

第一行是一个正整数 $N$（$2 < N < 6$），后面包含 $N$ 行由 $0$，$1$，$2$ 组成的 $N \times N$ 矩阵，其中 $0$ 表示可以走，$1$ 表示蝙蝠（不能走），$2$ 表示宝藏的位置。

注意：第一个房间（左上角）没有蝙蝠。

输出格式

一行，一个整数，表示可以找到宝藏的线路数。

样例输入 #1

6
0 0 1 1 0 0
1 0 0 1 0 0
0 0 0 1 2 0
0 1 1 1 0 0
0 0 0 1 0 0
0 0 0 1 0 0

样例输出 #1

0

样例输入 #2

2
0 0
0 2

样例输出 #2

5

数据范围

$2 < N < 6$，矩阵元素仅包含 $0$、$1$、$2$。第一个格子（左上角）保证不为 $1$。

知识点与难度

本题涉及的知识点从属于 GESP 六级（DFS 搜索、回溯、八方向路径计数），难度等级：Easy。

测试点分布