Problem1190--PIPI的旅行路线

1190: PIPI的旅行路线

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 409  Solved: 120
[Submit] [Status] [Web Board] [Creator:]

Description

在一个n*n的矩阵中,每个格子都有一个整数,PIPI位于矩阵的左上角,它想知道有多少条不同合法路线达到矩阵右下角。
行走规则如下:
(1)每次只能往下或往右走一步。
(2)格子中的整数表示从该点出发一步必须跨越的距离。


PS:对(1)和(2)条件的解释: 若此时在 (x,y) 并且格子上的数字为 k ,则下一步到达的位置为 (x+k,y)或 (x,y+k)

Input

多组数据
第一行为一个整数n,4<=n<=34.
接下来n行给出一个数字矩阵,0<=矩阵中元素<=9.

Output

对于每组数据输出一个整数,表示从左上角到右下角的不同路径数。

Sample Input

4
2331
1213
1231
3110
4
3332
1213
1232
2120
5
11101
01111
11111
11101
11101

Sample Output

3
0
7

Source/Category