Board Jump

Interview

Time limit1sMemory limit128 MB

Summary

Count distinct paths from top-left to bottom-right of an N×N grid where each cell's digit fixes the exact jump length right or down, using big-integer DP.

Level: Medium4 of 10
Topics: Dynamic programming, Matrix, Math
Solved: No attempts yet

Problem

You are given an N × N game board. Each cell holds a single digit from 0 to 9. A piece starts on the top-left cell and must reach the bottom-right cell.

The number written in a cell is the exact distance (jump length) you must move from that cell. You may only move to the right or downward, and you must move exactly that many cells to the right or exactly that many cells down. A cell containing 0 is a terminal cell from which no further move is possible.

Count the number of distinct paths that start at the top-left cell and reach the bottom-right cell while following these rules.

Input

The first line contains an integer N (4 ≤ N ≤ 100). Each of the next N lines contains N digits between 0 and 9, separated by spaces.

Output

Print, on a single line, the number of distinct paths from the top-left cell to the bottom-right cell that follow the rules. The number of paths may exceed $2^{63}-1$ , but it never has more than 100 digits.

Hint



Figure 1	Figure 2

Examples3

Example 1
Input
```
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0
```
Expected output
```
3
```
Example 2
Input
```
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 0
```
Expected output
```
20
```
Example 3
Input
```
4
0 1 1 1
1 1 1 1
1 1 1 1
1 1 1 0
```
Expected output
```
0
```