볼더링

Carl은 상자 안에서 몇 번이고 늦은 오후까지 미루며 밤새 비디오 게임만 하다가, 마침내 새해 결심을 실천할 때라고 결심했다. 바로 볼더링 클라이밍장에 가는 것이다.

그는 비교적 쉬운 벽 하나를 골라 올라가 보려 했지만, 항상 체력이 떨어져서 떨어지고 말았고 꼭대기에는 끝내 닿지 못했다.

오르는 동안 그는 홀드의 모양이 제각각이고 어떤 홀드는 잡기가 훨씬 어렵다는 것을 알아차렸다. 그래서 홀드를 잡는 데 드는 체력도 다르다. 답답해진 Carl은 볼더링장의 단골 중 한 명인 당신에게 벽을 오르는 방법을 물어본다. 체력이 바닥나지 않으면서 올라갈 수 있는 가장 짧은 경로를 알려 주자.

볼더링 벽은 한 변이 1 × 1인 정사각형 칸이 격자로 늘어선 형태이며, 각 칸에 홀드를 설치할 수 있다. 이 문제에서는 홀드의 크기가 다르다는 점은 고려하지 않으므로, 홀드는 칸의 정중앙에 있는 한 점이라고 생각하면 된다. Carl은 두 홀드 사이의 거리(칸 중심 사이의 유클리드 거리)가 팔이 닿는 거리를 넘지 않을 때에만 한 홀드에서 다른 홀드로 이동할 수 있다.

그림 B.1: 예제 테스트 1

입력은 다음과 같다.

• 네 정수 h, w, r, s가 주어지는 한 줄 (2 ≤ h ≤ 25, 1 ≤ w ≤ 25, 1 ≤ r ≤ 3, 1 ≤ s ≤ 10^9). h와 w는 볼더링 벽의 높이와 너비이고, r은 Carl의 팔이 닿는 거리이며, s는 Carl의 체력을 수치로 나타낸 것이다.
• 볼더링 벽의 홀드를 나타내는, 각각 w개의 문자로 이루어진 h개의 줄. 각 문자는 난이도 c (1 ≤ c ≤ 9)인 홀드가 그 위치에 설치되어 있음을 뜻하는 숫자 c이거나, 설치된 홀드가 없음을 뜻하는 “.”이다.

첫 번째 줄은 볼더링 벽의 맨 위에, 마지막 줄은 맨 아래에 대응한다.

홀드의 나열이 Carl에게 유효한 경로가 되려면 다음 조건을 만족해야 한다.

• 경로는 가장 아래쪽 홀드에서 시작해 가장 위쪽 홀드에서 끝난다. 가장 아래쪽 홀드와 가장 위쪽 홀드는 각각 유일하게 존재하며, 서로 다르다는 것이 보장된다.
• 경로에서 사용한 홀드의 난이도 합이 s 이하여야 한다.
• 경로를 따라 이웃한 두 홀드 사이의 유클리드 거리가 r 이하여야 한다.

체력이 바닥나지 않으면서 가장 위쪽 홀드에 도달할 수 있는 Carl의 최단 경로의 총 길이를 출력한다. 정답의 절대 오차 또는 상대 오차는 10^-6 이하여야 한다. Carl이 꼭대기에 도달할 수 없다면 impossible을 출력한다.