暂无测试数据。

题目描述

设有一个 \(N*N\) 方格的迷宫，
入口分别在左上角和右上角。
迷宫格子中分别放 0 和 1,
0 表示可通，1 表示不能通过，入口和出口肯定是 0。

迷宫走的规则如下：
即从某个点开始，
又八个方向可走，
前进方格中的数字为 0 时表示可以通过，
为 1 时表示不可通过，
要另找路径。
找出所有从入口（左上角）到出口（右上角）的路径（不能重复），
输出路径总数，
如果无法到达，则输出 0。

输入

一个整数 \(N\).
接下来 \(N\) 行，每行 \(N\) 个数字，0 或 1，描述迷宫。

输出

输出路径总数。

样例输入

3
0 0 0
0 1 1
1 0 0

样例输出

2

数据范围限制

\(2 \leq N < 10\)

来源

基础篇补充7.14