개발생각

import java.util.Scanner;

// Q) 점프
// #1890

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[][] board = new int[101][101];
		long[][] dp = new long[101][101];
		int[][] visit = new int[101][101];
		
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				board[i][j] = sc.nextInt();
			}
		}
		
		dp[0][0] = 1;
		visit[0][0] = 1;
		
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(i==n-1 && j==n-1){
					break;
				}
				if(visit[i][j] == 0) {
					continue;
				}
				int move = board[i][j];
				visit[i+move][j] = 1;
				visit[i][j+move] = 1;
				if(i+move<n){
					if(visit[i+move][j] == 1){
						/*System.out.println("move : "+move);
						System.out.println("board["+(i+move)+"]["+j+"]");*/
						dp[i+move][j] += dp[i][j];
						//visit[i+move][j] = 1;
					}
				}
				if(j+move<n){
					if(visit[i][j+move] == 1){
						/*System.out.println("@@move : "+move);
						System.out.println("@@board["+i+"]["+(j+move)+"]");*/
						dp[i][j+move] += dp[i][j];
						//visit[i][j+move] =1;
					}
				}
				
			}
		}
		System.out.println(dp[n-1][n-1]);
		
	}
}