그리디 알고리즘

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

요약

토러스 모양 격자에서 행이나 열 전체의 높이를 여러 번 올려, 높이가 같은 인접 칸 쌍의 수를 최대로 만드는 값을 구합니다.

난이도: 보통10점 중 7점
유형: 행렬, 그래프, 수학
정답자: 아직 제출이 없습니다

문제

나는 슈퍼 마리오 갤럭시 3를 하고 있다(복사본 고마워, 닌텐도). 대부분의 레벨은 구형의 작은 행성이지만, 보너스 레벨은 다르다. 보너스 레벨은 토러스 모양이다. 마주 보는 변 두 쌍을 각각 붙인 직사각형이라고 생각하면 된다. 8비트 시절 게임에 대한 오마주로, 행성의 표면은 작은 직사각형 격자이다. 격자의 각 칸에는 고유한 높이가 있다. 보너스 레벨은 두 부분으로 진행된다. 첫 번째 부분에서는 0번 이상의 연산을 적용해 레벨을 지형 변경(테라포밍)할 수 있다. 연산 하나는 격자의 행 또는 열을 하나 골라, 그 행이나 열에 있는 모든 칸의 높이를 1씩 올리는 것이다. 같은 행이나 열을 여러 번 골라도 되고, 서로 다른 행과 열을 골라도 된다. 이 연산은 원하는 만큼 몇 번이고 할 수 있다. 지형 변경 후에는 높이가 같은 두 칸이 맞닿은 변마다 코인이 나타나고, 이를 모을 수 있다. 플랫포밍에는 자신이 있어서 코인을 전부 모으는 것은 문제가 되지 않는다. 이 문제의 과제는 코인이 가장 많이 나타나도록 레벨을 지형 변경하는 알고리즘을 설계하는 것이다.

입력

첫 줄에는 격자의 크기를 나타내는 두 정수 $n$ 과 $m$ ( $2 \le n, m \le 50$ )이 주어진다. 다음 $n$ 개의 줄에는 모든 칸의 초기 높이가 주어진다. $i$ 번째 줄에는 정수 $h_{i1}, h_{i2}, \ldots, h_{im}$ 이 $m$ 개 주어지며, $h_{ij}$ 는 좌표 $(i, j)$ 에 있는 칸의 높이이다. 모든 높이는 0 이상 500 이하이다. 지형 변경 후에도 이 범위를 만족할 필요는 없다.

출력

레벨을 최적으로 지형 변경했을 때 나타날 수 있는 코인의 최대 개수를 정수 하나로 출력한다.

힌트

첫 번째 예제의 레벨을 최적으로 지형 변경한 모습이다:

예제3

예제 1
입력
```
2 3
1 2 3
4 5 99
```
예상 출력
```
8
```
예제 2
입력
```
3 3
3 2 4
2 2 3
5 4 6
```
예상 출력
```
14
```

예제 3

입력

예상 출력