====== 파이프 옮기기 2 ======

===== 풀이 =====
  * [[ps:problems:boj:17070]]에서 n의 크기만 늘린 문제. 풀이와 코드 모두 동일하다. 풀이는 [[ps:problems:boj:17070]] 참조

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 17069. 파이프 옮기기 2".

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

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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}