路径方案三

题目描述

给定一个 n*n​ 的方格迷宫，从左上角编号 ​(1,1) 至右下角编号 (n,n)​ 。

入口在左上角 ​(1,1) 处，出口在右上角 ​(1,n) 处。

迷宫格子中分别放 ​0 和 1​，​0 表示可通行，​1 表示不能通行，入口和出口处肯定是 ​。

迷宫走的规则如下：从某点开始，有八个方向（周围一圈）可走，前进方格中数字为 ​0 时表示可通过，为 ​1 时表示不可通过，要另找路径。

你的任务：找出所有从入口（左上角）到出口（右上角）的路径（没有重复的点），输出路径总数，如果无法到达，则输出 0​。

输入格式

第一行 n（1<n<10），接下来是 n 行 n 列由 1 和 ​0 组成的迷宫 ，相互之间用空格隔开。

输出格式

一行一个整数，为可行的路径方案总数。

样例输入 #1

3
0 0 0
0 1 1
1 0 0

样例输出 #1

2