[SWEA] 격자판의 숫자 이어붙이기

def dfs(row, col, cnt, ans):
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    if cnt == 7:
        answer.append(ans)
        return
    for i in range(4):
        now_dr = row + dr[i]
        now_dc = col + dc[i]
        if 0 <= now_dr < 4 and 0 <= now_dc < 4:
            tmp = ans
            ans += arr[now_dr][now_dc]
            dfs(now_dr, now_dc, cnt+1, ans)
            ans = tmp

T = int(input())
for TC in range(T):
    arr = [list(map(str, input().split())) for _ in range(4)]
    answer = []

    for i in range(4):
        for j in range(4):
            dfs(i, j, 0, '0')
    result = set(answer)
    a = len(result)

    print('#{} {}'.format(TC+1, a))