[백준] 1890번 점프 (silver 1

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[]args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int n=Integer.valueOf(br.readLine());
        long[][] num=new long[n+1][n+1];
        long[][] dp=new long[n+1][n+1];
        for(int i=1; i<=n; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                num[i][j]=Long.valueOf(st.nextToken());
                if((!(i==1 && j==1) && dp[i][j]==0) || (i==n && j==n)){
                    continue;
                }
                if(i+num[i][j]<=n){
                    dp[(int)(i+num[i][j])][j]= dp[i][j]==0 ? dp[(int)(i+num[i][j])][j]+1 : dp[(int)(i+num[i][j])][j]+dp[i][j] ;
                }
                if(j+num[i][j]<=n){
                    dp[i][(int)(j+num[i][j])]= dp[i][j]==0 ? dp[i][(int)(j+num[i][j])]+1 : dp[i][(int)(j+num[i][j])]+dp[i][j];
                }

            }
        }

        bw.write(dp[n][n]+"");
        bw.flush();


    }
}