시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 47 | 34 | 23 | 74.194% |
쇼핑을 매우 좋아하는 경곽이는 JOI시로 여행을 왔다. JOI시는 H행 W열로 구성된 격자 도시이다.
이 도시에 각 위치에는 가게가 있을 수 있다. 그리고 각 가게들은 모두 서로 다른 물건들을 판매한다.
경곽이는 (1, 1)에서 출발하여 (H, W)까지 이동할 예정이다. 가이드는 경곽이의 쇼핑 낭비를 최소화하기 위해서 JOI시에서 최단 경로로만 이동하려고 한다. 즉, 아래 또는 오른쪽으로만 이동할 예정이다.
경곽이는 각 위치에 도달하면 다음과 같이 쇼핑한다.
경곽이는 자신의 쇼핑 중독이 너무 심함을 알고 있기에 주변에 인접한 가게들에서는 적어도 한 가게에서는 쇼핑을 참는다 (ㅠㅠ) 따라서 인접한 곳 중에서는 한 곳만 제외한 나머지를 싹쓸이 한다.
이러한 경곽이가 최소한의 돈을 낭비할 수 있도록 JOI시의 (1, 1)에서 출발하여 (H, W)까지 안내하는 프로그램을 작성하는 것이 여러분의 목표이다.
경곽이가 쓰는 금액의 최솟값을 구하는 프로그램을 작성하시오.
첫 번째 줄에는 도시의 행과 열을 나타내는 정수 H, W가 공백으로 구분되어 입력된다. (3 ≦ H ≦ 1000, 3 ≦ W ≦ 1000)
다음 줄부터 H줄에 걸쳐서 W개로 이루어진 문자열이 입력된다.
이 값들은 상점의 정보를 나타낸다.
만약 그 칸이 "."라면 가게가 없음을 의미한다.
만약 그 칸의 값이 "1" ~ "9"로 표시되어 있다면, 그 위치에는 상점이 있고 그 상점에서 물건을 살 때 드는 비용을 의미한다.
목적지까지 경곽이가 최소한의 낭비를 하도록 이동했을 경우 경곽이가 사용한 금액을 출력한다.
5 5 ..483 .59.9 3.866 79... 4.8..
20
12 10 ..498522.4 .633527629 54.4621596 634.213458 1924518685 7739539767 276155.3.6 87716372.2 .858877595 7998739511 3438.5852. 568.9319..
63