시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 853 | 406 | 333 | 49.850% |
“OK 계획대로 되고 있어”
한국 힙합의 떠오르는 신성인 마미손은 악당 무리에게서 도망치고 있다. 악당 무리는 넉살, 스윙스, 창모 3명으로 이루어져 있다. 마미손은 도망치는 도중 R*C 크기의 미로를 만났고, 미로 안에 숨기로 했다. 뒤늦게 미로에 도착한 악당 무리는 마미손을 찾기 위해 뿔뿔이 흩어져 찾아보기로 했다. 이때 악당들은 항상 상하좌우로만 이동 가능하고, 이동 속도는 모두 같으며 칸 단위로만 이동 가능하다. 또한 악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다. 넉살, 스윙스, 창모는 서로 다른 지점에서 마미손을 찾기 시작하는데 이들은 세 명이 한 지점에서 모였을 때 걸린 시간이 최소가 되는 지점에 마미손이 숨어있다고 확신한다. 마미손은 숨기 이전에 악당들이 어디서 탐색을 시작할지 알고 있어 악당들이 찾아올 지점들을 피해 숨으려고 한다.
힘든 모험을 시작한 마미손. 이 모험에서 주인공은 절대 죽지 않는다는 것을 여러분이 마미손이 되어 보여주자! R*C 크기의 미로가 주어지고, 넉살, 스윙스, 창모의 시작 위치가 주어질 때, 한 지점에 세 악당이 모일 때 걸린 시간이 최소가 되는 지점을 마미손에게 알려주자.
첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다. (2 ≤ R, C ≤ 100) 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다. 숫자 0은 이동 가능한 길, 1은 벽을 나타낸다. 그 다음 줄부터 3개의 줄은 각각 넉살, 스윙스 창모의 위치(행, 열)를 나타내는 자연수 Xi, Yi가 (1 ≤ Xi ≤ R, 1 ≤ Yi ≤ C)주어진다. 악당들은 위치가 겹치지 않고, 항상 이동 가능한 길에서 출발한다. 맨 왼쪽 위의 위치는 (1, 1)이다.
첫째 줄에 한 지점에 세 악당이 모일 때 걸린 시간의 최소 값을 출력한다. 둘째 줄에는 그러한 지점의 개수를 출력한다. 만약 세 악당이 모일 수 있는 지점이 존재하지 않는다면 -1를 출력한다.
5 5 00011 01011 00110 00001 10100 1 1 5 5 5 2
4 1
7 7 0110011 0001101 0001011 1111101 0011000 0100111 0010110 1 4 5 5 6 4
-1
University > 한양대학교 > 제5회 한양대학교 프로그래밍 경시대회 > Beginner Division K번