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.

fig

Input

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

Output

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

Example 

Input:


2331
1213
1231
3110

Output:
3

Input:


3332
1213
1232
2120

Output:

0

Input:

5
11101
01111
11111
11101
11101
      
Output:
7


hide comments
npsabari: 2012-07-03 13:45:12

@~neo~ and EkiGenz: How can i miss your comments!! costed me 3 WA!! :(

LaFolle: 2012-02-20 13:33:03

Don't put new line after answer.

!(NULL): 2011-10-15 05:50:24

This problem should be in tutorial section.

[retired]grayluck: 2011-09-30 06:27:47

yes...no '\n' at the end of output..

~neo~: 2011-09-21 17:27:15

3 times WA only due to \n..!!

Gaurav Mittal: 2011-08-18 11:28:07

cant preview the image

Sandeep Gupta: 2011-08-09 18:03:34

Please add the image for understanding of the problem ....
The number in a cell represents move in one direction or could be both right & bottom ?

Ashish Khurange: 2011-04-06 04:32:34

Infinity, can you please upload the image? It is giving trouble to understand the problem.

biQar: 2011-03-26 04:13:52

why i get WA by printing '\n' in output ??? i don't understand the logic of the problem setter !!! x-(

kshitij agrawal: 2011-03-23 19:34:01

easy dp !! and n<11 ...

Last edit: 2011-03-23 19:34:49

Added by:Infinity
Date:2011-03-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 ASM64 BASH CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO ICON ICK LUA NEM NICE OCAML PIKE PRLG-swi SCM guile SCM qobi ST TCL WHITESPACE