cho.sh두부장수 장홍준 2
아직 제출이 없습니다시간 제한1초메모리 제한256 MB문제 설명
예제8
문제
장홍준은 두부장수다. 세로 크기가 N, 가로 크기가 M인 두부판을 2x1 크기의 두부로 잘라서 판다. 두부판은 칸마다 두부의 등급이 다르고, 2x1 두부 한 조각의 값은 그 조각이 덮는 두 칸의 등급으로 정해진다. 값은 다음 표를 따른다.
| A | B | C | D | F | |
|---|---|---|---|---|---|
| A | 10 | 8 | 7 | 5 | 1 |
| B | 8 | 6 | 4 | 3 | 1 |
| C | 7 | 4 | 3 | 2 | 1 |
| D | 5 | 3 | 2 | 2 | 1 |
| F | 1 | 1 | 1 | 1 | 0 |
표는 대칭이라서 두 칸의 순서는 값에 영향을 주지 않는다. 예를 들어 A 칸과 C 칸을 함께 덮는 두부의 값은 7이고, D 칸과 B 칸을 함께 덮는 두부의 값은 3이다.
잘라낸 두부 조각은 가로나 세로로 이웃한 두 칸을 덮고, 서로 겹칠 수 없다. 어느 조각에도 들어가지 않은 한 칸짜리 두부는 값이 0이므로 버린다. 홍준이가 두부판 하나에서 얻을 수 있는 두부 값의 합의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두부판의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 1 이상 50 이하의 정수다.
다음 N개 줄에는 각각 M개의 문자가 공백 없이 주어진다. 각 문자는 그 칸에 있는 두부의 등급이고 A, B, C, D, F 중 하나다.
출력
첫째 줄에 잘라낸 두부 값의 합의 최댓값을 출력한다.
Loading...