도미노 배치 찾기
시간 제한2초메모리 제한128 MB
8x7 격자를 28개의 도미노로 정확히 한 번씩 사용해 덮을 때, 각 도미노의 숫자 쌍이 칸의 값과 일치하는 배치 방법의 개수를 구합니다.
문제
각 도미노는 1×2 크기이며 두 개의 1×1 칸으로 이루어져 있다. 각 칸에는 0부터 6까지의 수가 하나 적혀 있다. 가능한 도미노는 숫자 쌍 (0,0), (0,1), ..., (6,6)으로 총 28개이며, (a,b)와 (b,a)는 같은 도미노로 본다.
8×7 격자의 각 칸에도 0부터 6까지의 수가 하나씩 적혀 있다. 28개의 도미노를 모두 한 번씩만 사용해서 격자를 빈틈없이 덮으려고 한다. 도미노를 놓은 두 칸의 수는 그 도미노의 두 수와 같아야 한다.
도미노는 회전할 수 있다. 같은 도미노를 두 번 이상 사용할 수 없다. 주어진 격자를 만들 수 있는 서로 다른 배치의 수를 구하라.
입력
총 8줄이 주어진다. 각 줄은 길이 7의 문자열이며, 각 문자는 0부터 6까지의 숫자이다.
출력
주어진 격자를 만들 수 있는 서로 다른 도미노 배치의 수를 출력한다.