6146번 - 신아를 만나러 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 300 | 206 | 186 | 73.810% |
문제
키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. 각각의 웅덩이는 (Ai, Bi)(|Ai| ≤ 500, |Bi| ≤ 500)에 위치해 있으며 키파는 눈이 좋아 이 웅덩이를 모두 볼 수 있다.
신아가 일찍 일어날 수도 있기 때문에 어서 (X, Y)에 있는 신아의 집에 최대한 빨리 도달해서 그녀가 잘 때 서프라이즈를 해 주고 싶지만, 장화가 새 것이기 때문에 웅덩이를 밟지 않는 것도 중요하다. 만일 키파가 상하좌우로만 이동할 수 있다면 웅덩이를 밟지 않으면서 신아에게 갈 수 있는 최소 거리는 얼마인가? 신아에게 가기 위해 웅덩이를 밟아야만 하는 경우는 없다고 가정한다.
입력
첫째 줄에 X, Y와 N이 공백을 사이에 두고 주어진다.
i+1 (1 ≤ i ≤ N) 번째 줄에 Ai와 Bi가 공백을 사이에 두고 주어진다.
출력
첫째 줄에 키파가 웅덩이를 밟지 않고 신아에게 갈 수 있는 최소 거리를 출력하라.
예제 입력 1
1 2 7 0 2 -1 3 3 1 1 1 4 2 -1 1 2 2
예제 출력 1
11
힌트
신아는 (1, 2)에 있다. 키파는 예제 입력에서 주어진 7개의 웅덩이를 모두 볼 수 있다.
4 . . . . . . . .
3 . M . . . . . .
Y 2 . . M B M . M .
1 . M . M . M . .
0 . . * . . . . .
-1 . . . . . . . .
-2-1 0 1 2 3 4 5
X
가장 짧은 거리는 아래 그림에서 *로 표시된 길이다.
4 ******* . . . .
3 * M . * . . . .
Y 2 * . M B M . M .
1 * M . M . M . .
0 ***** . . . . .
-1 . . . . . . . .
-2-1 0 1 2 3 4 5
X
출처
Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO December 2007 Contest > Silver 3번
- 문제를 번역한 사람: kipa00
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호