정육면체 접기

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

요약
2x2 블록 없이 연결된 여섯 개의 단위 정사각형 배치가 주어질 때, 이것을 정육면체로 접을 수 있는지 판정한다.
난이도

보통10점 중 7점

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

문제

단위 정사각형 여섯 개를 "십자" 모양으로 붙인 다음 정육면체로 접을 수 있다는 것은 잘 알려져 있다.

그렇다면 다른 모양으로 붙인 경우는 어떨까? 즉, 단위 정사각형 여섯 개를 일부 변을 따라 붙여 놓았을 때, 이 배치를 접어서 단위 정육면체를 만들 수 있는가?

입력

입력은 6줄로 이루어지며, 각 줄은 6개의 문자로 단위 정사각형의 초기 배치를 나타낸다. 각 문자는 빈 칸을 뜻하는 . 또는 단위 정사각형을 뜻하는 #이다.

#는 정확히 6번 나타나며 단위 정사각형을 나타낸다. 이들은 하나의 연결 성분을 이루므로, 어떤 #에서 다른 #으로 이동할 때 .을 밟지 않고 가로, 세로로만 움직여 도달하는 것이 가능하다. 또한 #만으로 이루어진 2 × 2 부분 정사각형은 존재하지 않는다. 즉, 다음과 같은 패턴은 입력에 나타나지 않는다.

##
##

출력

단위 정사각형을 정육면체로 접을 수 있으면 can fold를, 그렇지 않으면 cannot fold를 출력한다.

예제4

  1. 예제 1

    입력
    ......
    ......
    ######
    ......
    ......
    ......
    
    예상 출력
    cannot fold
    
  2. 예제 2

    입력
    ......
    #.....
    ####..
    #.....
    ......
    ......
    
    예상 출력
    can fold
    
  3. 예제 3

    입력
    ..##..
    ...#..
    ..##..
    ...#..
    ......
    ......
    
    예상 출력
    cannot fold
    
  4. 예제 4

    입력
    ......
    ...#..
    ...#..
    ..###.
    ..#...
    ......
    
    예상 출력
    can fold