시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 687 | 164 | 125 | 21.891% |
미노타우르스는 그리스 신화에 나오는 괴물로, 크레탄 미궁에 사는 소 머리에 인간의 몸을 하고 있는 괴물이다. 미노타우르스는 크레타의 사람들을 마구마구 잡아먹었고, 미노스 왕은 미노타우르스를 미궁에 가둬버렸다. 매년 일곱살 소년, 소녀는 미노타우르스에게 제물로 바쳐진다. 제물을 받는 시기가 끝나면, 괴물은 한동안 잠을 자고 있는다.
그리스의 용감한 영웅 테세우스는 미노타우르스를 잡기위해 미궁으로 들어갔다. 미노타우르스는 매우 잡기 어려운 괴물이기 때문에, 미궁을 막아 미노타우르스를 안에 가두려고 한다.
미궁은 동일한 정사각형 칸으로 나누어진 직사각형으로 나타낼 수 있다. 각 칸은 비어있거나 막혀있다. 미노타우르스는 막힌 칸으로 이동할 수 없다. 미궁의 입구는 네 꼭짓점 중 하나이고, 미노타우르스의 둥지는 입구의 반대편 꼭짓점에 있다.
테세우스는 미궁에 장애물을 하나 설치해 미노타우르스를 가두려고 한다. 장애물을 설치할 칸은 모두 비어있어야 한다. 미노타우르스의 둥지나 입구에는 장애물을 설치할 수 없다.
미노타우르스를 미궁에 가두는 가장 작은 정사각형 장애물의 크기와 위치를 구하는 프로그램을 작성하시오.
첫째 줄에 미궁의 너비와 높이 w, h가 주어진다. (2 ≤ w, h ≤ 1500)
다음 h개 줄에는 미궁의 지도가 주어진다. 각 줄은 w개 글자로 이루어져 있고, 빈 칸은 '.'으로, 막힌 칸은 '#' 로 나타낸다.
입구의 위치는 왼쪽 위 칸 (1,1) 이고, 미노타우르스의 둥지의 위치는 오른쪽 아래 칸 (w, h)이다. 두 칸은 항상 비어있으며, 입구에서 둥지로 가는 경로가 항상 존재한다.
세 정수 l, x, y를 출력한다. l은 미노타우르스를 미궁에 가두는 가장 작은 정사각형 장애물의 변의 길이이며, x, y는 장애물의 왼쪽 위 칸의 좌표이다. 가능한 좌표가 여러개인 경우에는 아무거나 출력한다. 장애물을 설치한 곳에 막힌 칸이 있으면 안되며, 입구와 둥지를 포함해도 안 된다. 만약, 장애물 하나로 미노타우르스를 미궁에 가둘 수 없으면, "Impossible"을 출력한다.
11 6 ......##### .#.#...#..# .#.#....... .......###. #####.###.. #####......
2 6 3
3 3 ... .#. ...
Impossible
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2012 L번