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

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

큐브

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

요약
n x n x n 격자에 적힌 문자들로 이루어진 조각들이 서로 맞물려 있어, 자르지 않고서는 큐브를 분리할 수 없는지 판정한다.
난이도

어려움10점 중 8점

유형
그래프, DFS, 기하, 구현
정답자
아직 제출이 없습니다

문제

여러 가지 모양의 단단한 조각들이 서로 맞물려 이루어진 큰 정육면체(큐브)를 생각해 보자. 조각들이 충분히 얽혀 있다면, 이들을 분리하는 유일한 방법은 일부 조각을 잘라 내는 것뿐일 수 있다. 우리는 다음과 같이 물을 수 있다. "이 큐브는 안정한가?" 즉, 어떤 조각도 변형하거나 자르지 않고서 큐브를 22개 이상의 덩어리로 분리하는 것이 물리적으로 불가능한가?

여러분의 프로그램은 이러한 여러 큐브에 대해 이 질문에 답해야 한다.

큐브를 이루는 조각들은 다음과 같이 주어진다. 큐브를 n×n×nn \times n \times n개의 작은 정육면체로 이루어진 격자로 나누고, 각 작은 정육면체에 대문자 한 글자를 붙인다. 면을 맞대고 인접한 두 작은 정육면체는 같은 문자로 표시되어 있을 때, 그리고 그럴 때에 한해 하나로 붙어 있다. 예를 들어 첫 번째 테스트 케이스의 큐브는 33개의 단단한 조각으로 이루어져 있다.

입력

프로그램에는 최대 1010개의 서로 다른 큐브의 명세가 주어진다. 각 명세의 처음 두 줄은 큐브의 크기 nn (1≤n≤10)(1 \le n \le 10)과 빈 줄로 이루어진다. 이어지는 n×(n+1)n \times (n + 1)개의 줄은 큐브의 nn개 수평 층을 아래에서 위로 나타낸다. 각 층의 명세는 그 층에 있는 각 작은 정육면체의 문자를 나타내는 n×nn \times n 정사각형과, 그 뒤의 빈 줄 하나로 이루어진다. 입력에는 공백이 없다. 입력은 한 줄에 홀로 놓인 숫자 00으로 끝난다.

출력

주어진 각 큐브에 대해, 주어진 순서대로 그 큐브가 안정하면 Yes를, 그렇지 않으면 No를 출력한다.

예제5

  1. 예제 1

    입력
    2
    
    AB
    AB
    
    BB
    BA
    
    3
    
    AAA
    BBB
    AAA
    
    AAA
    ABA
    AAA
    
    ABA
    ABA
    ABA
    
    0
    
    예상 출력
    No
    Yes
    
  2. 예제 2

    입력
    1
    
    A
    
    0
    
    예상 출력
    Yes
    
  3. 예제 3

    입력
    3
    
    AAA
    BBB
    AAA
    
    AAA
    ABA
    AAA
    
    ABA
    ABA
    ABA
    
    0
    
    예상 출력
    Yes
    
  4. 예제 4

    입력
    1
    
    A
    
    2
    
    AB
    AB
    
    BB
    BA
    
    0
    
    예상 출력
    Yes
    No
    
  5. 예제 5

    입력
    3
    
    AAA
    BBB
    AAA
    
    AAA
    ABA
    AAA
    
    ABA
    ABA
    ABA
    
    1
    
    Q
    
    2
    
    AA
    AA
    
    BB
    BB
    
    0
    
    예상 출력
    Yes
    Yes
    No