题目描述

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

输入格式

第一行正整数 N（2 < N ≤ 10），后面 N×N 行由 0、1、2 组成的矩阵。

输出格式

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

样例

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

12

说明/提示

进入格子时标记 vis，到达宝藏（值为 2）计数 +1，离开当前格子时取消标记（回溯），这样才能数出所有不同路径。