SP8598 TRAVERSE - Traverse through the board

An n x n game board is filled with integers, one positive integer per square. The objective is to travel along any legitimate path from the upper left corner to the lower right corner of the board. Rules 1.The number in any one square describes how far a step away from that location must be. 2.If the step size moves out of the game board, then that step is not allowed. 3.All steps must be either to the right or towards the bottom. Note that a 0 is a dead end which prevents any further progress. Consider the 4 x 4 board shown in Figure 1, where the solid circle identifies the start position and the dashed circle identifies the target. Figure 2 shows the three paths from the start to the target, with the irrelevant numbers in each removed.

The first line contains the value of n followed by a nxn matrix depicting the board configuration.

The output consists of a single integer, which is the number of paths from the upper left corner to the lower right corner.