BOJ - 4620 - Pascal’s Travels

import sys


def solution():
    while True:
        N = int(input())
        if N == -1: return

        dx = [0, 1]
        dy = [1, 0]
        maps = []
        for _ in range(N):
            maps.append(list(sys.stdin.readline().strip()))

        dp = [[0 for _ in range(N)] for _ in range(N)]
        dp[0][0] = 1
        for i in range(N):
            for j in range(N):
                if i == N - 1 and j == N - 1: continue

                mul = int(maps[i][j])

                for k in range(2):
                    nx = i + dx[k] * mul
                    ny = j + dy[k] * mul
                    if nx < N and ny < N:
                        dp[nx][ny] += dp[i][j]

        print(dp[-1][-1])

solution()

https://www.acmicpc.net/problem/4620