미노타우르스는 그리스 신화에 나오는 괴물로, 크레탄 미궁에 사는 소 머리에 인간의 몸을 하고 있는 괴물이다. 미노타우르스는 크레타의 사람들을 마구마구 잡아먹었고, 미노스 왕은 미노타우르스를 미궁에 가둬버렸다. 매년, 일곱살 소년, 소녀는 미노타우르스에게 제물로 바쳐져야 한다. 제물을 받는 시기가 끝나면, 괴물은 한동안 잠을 자고 있는다.

그리스의 용감한 영웅 테세우스는 미노타우르스를 잡기위해 미궁으로 들어갔다. 미노타우르스는 매우 잡기 어려운 괴물이기 때문에, 미궁을 막아 미노타우르스를 안에 가두려고 한다.

미궁은 동일한 정사각형 칸으로 나누어진 직사각형으로 나타낼 수 있다. 각 칸은 비어있거나 막혀있다. 미노타우르스는 막힌 칸으로 이동할 수 없다. 미궁의 입구는 네 꼭짓점 중 하나이고, 미노타우르스의 둥지는 입구의 반대편 꼭짓점에 있다.

테세우스는 미궁에 장애물을 하나 설치해 미노타우르스를 가두려고 한다. 장애물을 설치할 칸은 모두 비어있어야 한다. 미노타우르스의 둥지나 입구에는 장애물을 설치할 수 없다.

미노타우르스를 미궁에 가두는 가장 작은 정사각형 장애물의 크기와 위치를 구하는 프로그램을 작성하시오.

#4374 upload 49 done 4 how_to_reg 4 auto_awesome スペシャルジャッジ

미노타우르스 미궁 timer 1s memory 128MB

#4374
スペシャルジャッジ

미노타우르스 미궁 1s 128MB