八个方向统计线路

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

输入格式

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

输出格式

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

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

0

数据范围

时间限制: 1000ms

内存限制: 256MB