만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

짝 맞추기 게임의 보드 배치

면접 대비

시간 제한1초메모리 제한1024 MB

요약
4x4 보드에서 각 쌍의 칸 위치 차이가 주어진 네 가지 상대 위치 중 하나인 짝짓기의 개수를 셉니다.
난이도

보통10점 중 5점

유형
백트래킹, 완전 탐색
정답자
아직 제출이 없습니다

문제

결혼식 피로연을 준비해야 한다. 피로연 프로그램에는 신랑과 신부가 함께 하는 짝 맞추기 게임이 들어간다. 이 게임은 피로연을 즐겁게 하려고 진행하므로, 배치는 쉬워야 한다.

짝 맞추기 게임에는 4x4 보드와 'A'부터 'H'까지 표시한 8쌍의 카드가 있다.

   +---+---+---+---+   A A B B
   |   |   |   |   |   C C D D
   +---+---+---+---+   E E F F
   |   |   |   |   |   G G H H
   +---+---+---+---+
   |   |   |   |   |
   +---+---+---+---+
   |   |   |   |   |
   +---+---+---+---+

게임을 시작하려면 16장의 카드를 모두 뒷면이 보이게 보드에 놓아야 한다. 예를 들면 다음과 같다.

   +---+---+---+---+
   | A | B | A | B |
   +---+---+---+---+
   | C | D | C | D |
   +---+---+---+---+
   | E | F | G | H |
   +---+---+---+---+
   | G | H | E | F |
   +---+---+---+---+

게임의 목표는 다음 과정을 반복해서 가능한 한 많은 카드를 앞면으로 드러내는 것이다. (1) 카드 두 장을 뒤집는다. (2) 두 카드가 같으면 앞면으로 두고, 다르면 다시 뒷면으로 되돌린다.

배치를 단순하게 유지하려면 보드의 모든 쌍이 다음 조건을 만족해야 한다. 쌍을 이루는 한 카드에서 다른 카드까지의 상대 위치가 주어진 4개의 상대 위치 중 하나여야 한다. 4개의 상대 위치는 서로 다르며, 아래 24개의 후보 중에서 고른다.

                                      (1, 0), (2, 0), (3, 0),
   (-3, 1), (-2, 1), (-1, 1), (0, 1), (1, 1), (2, 1), (3, 1),
   (-3, 2), (-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (3, 2),
   (-3, 3), (-2, 3), (-1, 3), (0, 3), (1, 3), (2, 3), (3, 3).

이 문제에서는 위 조건을 만족하는 보드 배치의 총 개수를 세는 프로그램을 작성한다. 같은 패턴의 배치는 한 번만 센다. 두 배치는 카드 쌍의 위치를 여러 번 서로 바꿔서 한쪽에서 다른 쪽을 만들 수 있으면 같은 패턴이다. 예를 들어 상대 위치가 (-2, 1), (-1, 1), (1, 1), (1, 2)로 주어지면 조건을 만족하는 배치는 두 개다.

  A B C D      A B C D
  B A D C      B D E C
  E F G H      F A G H
  F E H G      G F H E

첫 번째 배치의 상대 위치는 A:(1, 1), B:(-1, 1), C:(1, 1), D:(-1, 1), E:(1, 1), F:(-1, 1), G:(1, 1), H:(-1, 1)이다. 두 번째 배치의 상대 위치는 A:(1, 2), B:(-1, 1), C:(1, 1), D:(-2, 1), E:(1, 2), F:(1, 1), G:(-2, 1), H:(-1, 1)이다. 따라서 패턴의 총 개수는 2이다.

입력

입력에는 여러 개의 데이터 세트가 들어 있다. 각 데이터 세트는 한 줄에 다음 형식으로 주어진다.

x1 y1 x2 y2 x3 y3 x4 y4

i번째 상대 위치는 (xi,yi)(x_i, y_i)이다. 주어진 상대 위치는 서로 다르며, 각각 24개의 후보 중 하나이다. 입력의 끝은 4보다 큰 수 하나만 적힌 줄로 표시한다.

출력

각 데이터 세트마다 패턴의 총 개수를 한 줄에 출력한다. 다른 문자나 줄을 출력하지 않는다. 앞뒤 공백은 허용된다.

예제1

  1. 예제 1

    입력
    -2 1 -1 1 1 1 1 2
    1 0 2 1 2 2 3 3
    5
    
    예상 출력
    2
    15