Rock Climbing

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

요약

격자에서 어떤 E 칸에서 출발해 어떤 S 칸에 도착할 때, 각 칸의 값을 잃으면서 에너지가 음수가 되지 않는 최소 시작 에너지를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 동적 계획법
정답자: 아직 제출이 없습니다

문제

Peter is attempting to deep-water solo a rock climbing cliff over the ocean. Deep-water soloing (DWS) is a form of solo rock climbing that relies solely upon the presence of water at the base of the climb to protect against injury from falling.

Rock climbing is very exhausting and takes lots of energy. Since Peter is not very flexible, he can only move $1$ unit in any of the four directions: Up, Down, Left, and Right. Traveling to a different square will decrease Peter's energy by the amount on that square. Note that the amount of energy on a square can be negative. In this case, Peter will gain energy.

If Peter's energy is negative, he will fall into the water.

Peter doesn't want to get wet, so he asks you how much energy he needs to complete the climb, assuming he takes the best route.

입력

The first line of the input will contain two integers, $R$ , $C$ $(1 \leq R, C \leq 15)$ . The second line of input will consist of a row of $C$ E characters, separated by spaces, representing the top of the cliff. These take $0$ units of energy to enter. Peter can choose any of them.

Next, there will be $R$ rows of $C$ columns of numbers $X\_{r,c}$ , where $(-9 \leq X\_{r,c} \leq 9)$ , the energy required to enter that section of cliff. The final line of input will consist of a row of $C$ S characters, representing the possible start points of the climb. These take $0$ units of energy to enter. Returning to a starting position is allowed.

출력

Output a single integer, the amount of energy necessary to complete the climb without falling.

예제2

예제 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

예상 출력

예제 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

예상 출력