• 그리드의 한 모퉁이에서 대각선 모퉁이까지의 최단 이동 경로의 갯수를 세는 것은 2차원 DP의 대표적인 연습문제이다. 거기에서 약간의 변형을 추가한 문제.
  • 사실 이 문제는 n값이 작아서 그냥 그래프 탐색으로도 풀수 있기는 하다. n값을 늘린 파이프 옮기기 2는 DP로만 풀이 가능.
• 특정 셀까지 도달하는 경로의 갯수를 그 셀에 도달했을때까지의 방향별로 따로 구해주면 된다. DP table이 N*N*3 의 크기가 된다고 생각하면 된다.
• 그러한 DP table을 채우는 점화식을 세우는 것은 간단하게 나온다. (r,c) 좌표에 대한 DP값은 (r-1,c-1), (r-1,c), (c-1,r)의 세 좌표의 DP값만 갖고도 계산이 가능하고, r-1 보다 이전 열에 대한 정보는 필요가 없으니까므로, 각 열 별로 토글링을 하면서 구현이 가능하다
• N*N*3 크기의 테이블을 채워야 하고, 한칸을 계산하는데 O(1)이므로 총 시간 복잡도는 O(N*N)이 된다.

"""Solution code for "BOJ 17070. 파이프 옮기기 1".

- Problem link: https://www.acmicpc.net/problem/17070
- Solution link: http://www.teferi.net/ps/problems/boj/17070

Tags: [DP]
"""

WALL = '1'


def main():
    N = int(input())
    grid = [input().split() for _ in range(N)]
    dp_hor_cur, dp_ver_cur, dp_diag_cur = [0] * N, [0] * N, [0] * N
    dp_hor_cur[1] = 1
    for c in range(2, N):
        dp_hor_cur[c] = 0 if grid[0][c] == WALL else dp_hor_cur[c - 1]
    for r in range(1, N):
        dp_hor_prev, dp_hor_cur = dp_hor_cur, [0] * N
        dp_ver_prev, dp_ver_cur = dp_ver_cur, [0] * N
        dp_diag_prev, dp_diag_cur = dp_diag_cur, [0] * N
        for c in range(1, N):
            if grid[r][c] == WALL:
                continue
            dp_hor_cur[c] = dp_hor_cur[c - 1] + dp_diag_cur[c - 1]
            dp_ver_cur[c] = dp_ver_prev[c] + dp_diag_prev[c]
            if WALL not in (grid[r - 1][c], grid[r][c - 1]):
                dp_diag_cur[c] = (dp_hor_prev[c - 1] + dp_ver_prev[c - 1] +
                                  dp_diag_prev[c - 1])

    print(dp_hor_cur[-1] + dp_ver_cur[-1] + dp_diag_cur[-1])


if __name__ == '__main__':
    main()