차세대 지능형 교통시스템

import sys

n, T = map(int, sys.stdin.readline().split())

signals = []
for i in range(n*n):
    signals += list(map(int, sys.stdin.readline().split())),

inters = [[[0]*4 for x in range(n)] for y in range(n)]

rows = len(signals)
cols = len(signals[0])

for iidx in range(n*n):
    y = iidx//n
    x = iidx%n
    for t in range(4):
        inters[y][x][t] = signals[iidx][t]

signal_ways = {
    1: [(0, 1), [(-1, 0), (0, 1), (1, 0)]],
    2: [(-1, 0), [(0, -1), (-1, 0), (0, 1)]],
    3: [(0, -1), [(-1, 0), (0, -1), (1, 0)]],
    4: [(1, 0), [(0, -1), (1, 0), (0, 1)]],
    5: [(0, 1), [(-1, 0), (0, 1)]],
    6: [(-1, 0), [(0, -1), (-1, 0)]],
    7: [(0, -1), [(0, -1), (1, 0)]],
    8: [(1, 0), [(1, 0), (0, 1)]],
    9:  [(0, 1), [(0, 1), (1, 0)]],
    10: [(-1, 0), [(-1, 0), (0, 1)]],
    11: [(0, -1), [(-1, 0), (0, -1)]],
    12: [(1, 0), [(0, -1), (1, 0)]]
}
       
visited = set()

def dfs(y, x, t, dir):
    visited.add((y, x))

    if t == T:
        return 1
    
    sig_num = inters[y][x][t%4]
    valid_dir, next_coords = signal_ways[sig_num]

    if dir != valid_dir:
        return 1

    cnt = 1
    
    for oy, ox in next_coords:
        if not (0 <= y + oy < n and 0 <= x + ox < n):
            continue

        cnt += dfs(y + oy, x + ox, t + 1, (oy, ox))

    return cnt

cnt = dfs(0, 0, 0, (-1, 0))
print(len(visited))