'''
=input=
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
=dp print=
[[0, 0, 0], [1, 0, 0], [1, 0, 0], [1, 0, 0]]
[[0, 0, 0], [0, 0, 0], [0, 0, 1], [1, 0, 1]]
[[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 1]]
[[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 2, 1]]
=output=
3
'''
import sys
result = []
n = int(sys.stdin.readline().rstrip())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[[0, 0, 0] for _ in range(n)] for _ in range(n)]
dp[0][1][0] = 1
# 첫 번째 행 가로이동
for i in range(1, n):
# 벽이 있으면 break
if graph[0][i] == 1:
break
dp[0][i][0] = 1
for i in range(1, n):
for j in range(2, n):
if graph[i][j] == 0:
dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2] #노랑
dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2] #녹색
# 대각선은 빈 칸 조건 추가적으로 검증
if graph[i][j - 1] == graph[i - 1][j] == 0: #파랑
dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]
print(sum(dp[-1][-1]))
문제에 주어진 그림속에 점화식이 구현되어 있다. 3차원 DP 테이블도 나오는 구나 생각했다.
dp[i][j][0]
= 가로 형태인 파이프의 머리가 [i][j]칸에 위치할 수 있는 경우의 수
dp[i][j][0]
= ... 세로
dp[i][j][0]
= ... 대각선