아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

제비꽃 퍼즐

시간 제한5초메모리 제한128 MB

요약
주어진 조각들을 n×m 직사각형에 회전시켜 배치하되 맞닿는 변은 볼록과 오목이 짝을 이루고 테두리 변은 평평하도록 맞추는 경우의 수를 센다.
난이도

보통10점 중 7점

유형
백트래킹, 구현, 비트 연산
정답자
아직 제출이 없습니다

문제

퍼즐 맞추기를 좋아하시나요? 좋아하지 않아도 괜찮습니다. 이 문제에서 여러분이 할 일은 퍼즐을 직접 맞추는 것이 아니라, 퍼즐을 올바르게 맞출 수 있는 방법의 수를 세는 것입니다.

n×mn \times m개의 퍼즐 조각이 주어집니다. 각 조각은 정사각형이며 네 개의 변을 가집니다. 각 변은 다음 세 가지 종류 중 하나입니다.

  • 평평한 변
  • 볼록 변(돌기)
  • 오목 변(홈)

두 조각은 서로 맞닿는 변 중 하나가 볼록 변이고 다른 하나가 오목 변일 때에만 이어 붙일 수 있습니다(돌기가 홈에 끼워집니다). 조각은 90∘90^\circ 단위로 자유롭게 회전할 수 있지만, 뒤집을 수는 없습니다.

모든 조각이 n×mn \times m 크기의 직사각형을 이루고, 두 조각이 맞닿는 모든 곳에서 한 변은 볼록 변, 다른 한 변은 오목 변일 때 퍼즐이 올바르게 맞춰졌다고 합니다. 직사각형의 바깥 테두리에 놓인 변은 어떤 조각과도 맞닿지 않으므로, 테두리에 놓인 모든 변은 반드시 평평한 변이어야 합니다.

모든 조각의 색은 같으므로, 두 배치는 직사각형 전체에 나타나는 볼록 변과 오목 변의 배열이 서로 다를 때에만 서로 다른 것으로 봅니다. 직사각형의 방향은 고정되어 있으므로, 어떤 배치를 회전하여 다른 배치를 얻을 수 있더라도 두 배치는 서로 다른 것으로 셉니다.

올바르게 맞출 수 있는 서로 다른 방법의 수를 구하세요.

입력

첫째 줄에 테스트의 개수 dd (1≤d≤1001 \le d \le 100)가 주어집니다.

각 테스트는 두 정수 nn과 mm (1≤n≤61 \le n \le 6, 1≤m≤51 \le m \le 5)이 적힌 줄로 시작합니다. 이어지는 n×mn \times m개의 줄에는 조각의 정보가 주어집니다. 각 조각은 시계 방향으로 나열한 네 변의 종류를 나타내는 네 정수로 주어지며, 00은 평평한 변, 11은 볼록 변(돌기), 22는 오목 변(홈)을 뜻합니다.

출력

각 테스트마다 올바르게 맞출 수 있는 서로 다른 방법의 수를 한 줄에 하나씩 출력하세요.

참고

아래 그림은 한 조각 묶음을 올바르게 맞춘 한 가지 예시를 보여 줍니다.

올바르게 맞춘 퍼즐의 예시

예제4

  1. 예제 1

    입력
    2
3 3
0 0 1 2
0 0 1 2
0 0 1 2
0 0 1 2
0 1 1 2
0 1 1 2
0 1 1 2
0 1 1 2
2 2 2 2

3 3
0 0 1 2
0 0 1 2
0 0 1 2
0 0 1 2
0 1 1 2
0 1 1 2
0 1 1 2
0 1 2 2
2 2 2 2
    예상 출력
    1
0

  2. 예제 2

    입력
    2
1 1
0 0 0 0
1 1
0 0 0 1
    예상 출력
    1
0

  3. 예제 3

    입력
    1
1 2
0 0 0 1
0 0 0 2
    예상 출력
    2

  4. 예제 4

    입력
    1
2 2
0 0 1 2
0 0 1 2
0 0 1 2
0 0 1 2
    예상 출력
    1