Kuubi kleepimine

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

요약
10x10 격자 위 여섯 단위 정사각형이 주어질 때 이 도형이 정육면체로 접히는지 판정하고, 잘린 모서리에 접착용 띠의 위치를 정한다.
난이도

어려움10점 중 8점

유형
구현, 기하, DFS, 완전 탐색
정답자
아직 제출이 없습니다

문제

Jukul on vaja valmistada paberist kuup. Paberile on juba joonestatud 10×1010 \times 10 ruudustik, mille alumise vasaku ruudu koordinaadid on (1,1)(1,1) ja ülemise parema omad (10,10)(10,10). Juku valib 6 paarikaupa erinevat ruutu.

Kontollida, kas valitud ruutudest on võimalik kokku voltida kuup (lõigata ja voltida tohib ainult mööda olemasolevaid jooni).

Lisaks leida, milliste ruutude servadesse tuleks jätta kleepimiseks ribad. Kahest omavahel kokkupuutuvast lõikeservast tuleb riba jätta täpsele ühele. Ribad võivad asuda ka ruudustiku servas.

입력

Tekstifail sisaldab täpselt 6 rida, igal real kaks tühikuga eraldatud täisarvu: Juku valitud ruutude koordinaadid x_ix\_i ja y_iy\_i (1≤x_i≤101 \le x\_i \le 10, 1≤y_i≤101 \le y\_i \le 10).

출력

Tekstifaili esimesele reale väljastada JAH, kui Juku valitud ruutude väljalõikamisel moodustub (sidus) kujund, millest on võimalik kokku voltida kuup, vastasel juhul EI. Kui kuubi voltimine on võimalik, väljastada järmistele ridadele programmi poolt leitud kleepimisribade asukohad: tühikutega erladatult ruudu X- ja Y-koordinaadid ning suund (N --- üles, E --- paremale, S --- alla, W --- vasakule).

예제2

  1. 예제 1

    입력
    3 1
3 2
4 2
2 3
3 3
2 4
    예상 출력
    JAH
4 2 N
4 2 S
4 2 E
3 1 W
3 1 S
3 2 W
3 3 N

  2. 예제 2

    입력
    1 2
2 2
3 2
4 2
2 3
4 3
    예상 출력
    EI