폴리큐브의 겉넓이

면접 대비

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

요약

주어진 순서대로 단위 큐브를 놓을 때 원점에서 시작해 항상 이전 큐브와 면으로 연결되는지 검사하고, 유효하면 표면적을 아니면 위반한 첫 큐브 번호를 출력합니다.

난이도: 보통10점 중 4점
유형: 시뮬레이션, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

폴리큐브는 모서리 길이가 1인 단위 정육면체들을 면과 면이 맞닿도록 붙여 만든 입체이다. 선이나 꼭짓점으로만 닿는 경우는 폴리큐브가 아니다.

폴리큐브를 이루는 각 정육면체의 중심은 3차원 공간의 정수 좌표에 있다.

주어진 순서대로 정육면체를 하나씩 놓아 폴리큐브를 만든다고 하자. 첫 번째 정육면체는 반드시 (0, 0, 0)에 있어야 한다. 이후의 정육면체는 이전에 놓인 정육면체들 중 적어도 하나와 면을 공유해야 하며, 같은 좌표의 정육면체가 이미 놓여 있으면 안 된다.

주어진 좌표 순서가 폴리큐브를 만들 수 있는 순서인지 판단하라. 만들 수 있다면 완성된 폴리큐브의 겉넓이를 구하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 1,000)

각 테스트 케이스의 첫째 줄에는 정육면체의 개수 P가 주어진다. (1 ≤ P ≤ 100)

그다음에는 정육면체 중심 좌표 P개가 주어진다. 좌표는 x,y,z 형식이며, 한 줄에 최대 8개씩 공백으로 구분되어 주어진다.

입력으로 주어지는 모든 좌표 값은 0 이상 4 이하의 정수이다.

출력

각 테스트 케이스마다 한 줄을 출력한다.

주어진 순서로 폴리큐브를 만들 수 있다면 그 폴리큐브의 겉넓이를 출력한다.

만들 수 없다면 NO k를 출력한다. 여기서 k는 조건을 처음으로 만족하지 못한 정육면체의 번호이다. 첫 번째 정육면체의 번호는 1이다.

예제1

예제 1

입력

4
5
0,0,0 0,0,1 0,0,2 0,0,3 0,0,4
8
0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0 1,1,1
4
0,0,0 0,0,1 1,1,0 1,1,1
20
0,0,0 0,0,1 0,0,2 0,1,2 0,2,2 0,2,1 0,2,0 0,1,0
1,0,0 2,0,0 1,0,2 2,0,2 1,2,2 2,2,2 1,2,0 2,2,0
2,1,0 2,1,2 2,0,1 2,2,1

예상 출력