统计线路

题目描述

一个 $N \times N$ 的迷宫方格，在方格内"0"表示可以走，"1"表示不能行走，"2"表示宝藏。现在从左上角 $(1,1)$ 的位置进入迷宫寻找宝藏。统计有多少条线路可以找到宝藏（每条线路经过的格子只能访问 $1$ 次）。注意：第一个格子不为 $1$。

输入格式

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

输出格式

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

样例输入 #1

5
0 0 1 1 0
1 0 0 0 0
0 0 0 0 2
0 1 1 0 0
0 0 0 1 0

样例输出 #1

12

样例输入 #2

2
0 0
0 2

样例输出 #2

2

数据范围

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

知识点与难度

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

测试点分布