sohyunzzq   1년 전

문제

USC에는 다양한 맛있는 점심 식사 옵션이 있다. 가끔 점심을 먹으러 나갈 때 친구들과 만나고 싶을 때가 있는데, 그럴 때는 캠퍼스 내 여러 만남의 장소와 식당 중 하나를 선택할 수 있다. 하지만 어떤 식당을 가느냐에 따라 걸어야 하는 총 거리를 최소화하도록 어디에서 만날지를 신중하게 계획해야 한다.

더 정확히 말하면, 캠퍼스의 지도와 함께 특정 위치들이 만남의 장소 또는 식당으로 표시되어 주어진다. 또한 당신 자신과 점심을 함께 먹을 친구들의 출발 지점이 주어진다. 만남의 장소와 식당이 선택되면, 당신과 친구들은 각각의 출발 지점에서 만남의 장소로, 그 다음 식당으로, 그리고 다시 각자의 출발 지점으로 돌아오게 된다. 따라서 당신은 모든 사람의 이동 거리 합이 최소가 되는 만남의 장소와 식당 쌍을 선택하고자 한다.

입력

첫 번째 줄에는 정수 K (K ≥ 1)가 주어지며, 이는 입력 데이터 세트의 개수이다. 이후 K개의 데이터 세트가 주어진다. 각 데이터 세트는 다음과 같은 형태이다.

  • 첫 번째 줄: 캠퍼스 지도의 높이 h와 너비 w (1 ≤ h, w ≤ 30)
  • 다음 h개의 줄: 각 줄에는 w개의 문자로 이루어진 캠퍼스 지도

지도에서 각 문자는 다음 중 하나이다.

  • X — 접근할 수 없는 구역(건물이나 울타리 등)
  • . — 접근 가능한 구역
  • R — 식당이 있는 구역 (통과할 수 없지만 인접한 구역에서 들어가거나 나올 수 있음)
  • M — 만남의 장소 (통과 가능)
  • S — 당신 또는 친구의 출발 지점 (통과 가능)

이동은 상하좌우 네 방향으로만 가능하며, 대각선 이동은 불가능하다.

출력

각 데이터 세트마다 “Data Set x:”를 출력한다 (x는 데이터 세트 번호). 그 다음 줄에는 선택된 만남의 장소와 식당 쌍에 대해 당신과 모든 친구들이 이동한 총 거리를 출력한다. (이동 경로 자체는 출력하지 않아도 된다.)

만남의 장소나 식당이 존재하지 않거나, 모든 출발 지점에서 접근할 수 없는 경우 “Impossible”을 출력한다.

좋은 번역 감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.