만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

암벽 등반

시간 제한1초메모리 제한1024 MB

요약
S 칸에서 출발해 E 칸으로 올라가는 경로 중 필요한 에너지가 가장 적은 값을 구합니다.
난이도

보통10점 중 4점

유형
최단 경로, 그래프, 행렬
정답자
아직 제출이 없습니다

문제

페터는 바다 위에 있는 암벽을 로프 없이 오르려 한다. 딥워터 솔로(DWS)는 암벽 아래에 물이 있다는 점에 기대어, 떨어졌을 때 부상을 막는 단독 암벽 등반 방식이다.

암벽 등반은 매우 지치고 많은 에너지가 든다. 페터는 유연하지 않아서 상, 하, 좌, 우 네 방향 중 한 방향으로 11칸씩만 이동할 수 있다. 다른 칸으로 이동하면 그 칸에 적힌 값만큼 페터의 에너지가 줄어든다. 이 값은 음수일 수 있으며, 그때 페터는 에너지를 얻는다.

페터의 에너지가 음수가 되면 그는 물에 빠진다. 페터는 물에 젖고 싶지 않아서, 최적의 경로를 택했을 때 등반을 끝내는 데 필요한 에너지를 알고 싶어 한다.

입력

첫째 줄에 두 정수 RR과 CC (1≤R,C≤15)(1 \leq R, C \leq 15)가 주어진다. 둘째 줄에는 암벽의 맨 위를 나타내는 CC개의 문자 E가 공백으로 구분되어 주어진다. 이 칸에 들어가는 데는 00의 에너지가 든다. 페터는 이 중 어느 칸이든 고를 수 있다.

이어서 RR개의 줄에 각각 CC개의 정수 Xr,cX_{r,c}가 주어진다. (−9≤Xr,c≤9)(-9 \leq X_{r,c} \leq 9)이며, 암벽의 해당 구간에 들어가는 데 필요한 에너지다. 마지막 줄에는 등반을 시작할 수 있는 후보 지점을 나타내는 CC개의 문자 S가 공백으로 구분되어 주어진다. 이 칸에 들어가는 데는 00의 에너지가 든다. 시작 지점으로 다시 돌아오는 것도 허용된다.

출력

떨어지지 않고 등반을 끝내는 데 필요한 에너지를 나타내는 정수 하나를 출력한다.

예제2

  1. 예제 1

    입력
    5 5
E E E E E
1 2 3 4 5
5 4 3 2 1
-2 -2 -2 -2 -2
8 8 8 8 8
9 9 9 9 9
S S S S S
    예상 출력
    17

  2. 예제 2

    입력
    13 5
E E E E E
1 1 1 1 1
1 1 1 2 1
9 9 9 9 1
1 1 1 9 1
1 9 1 1 1
1 9 9 9 9
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
9 6 7 8 9
-5 9 -7 9 -5
6 0 7 0 5
S S S S S
    예상 출력
    32