문제
사막 지역에 새로운 유전이 발견되었다! 지질 분석관이 사막의 정보를 파악한 결과 기름이 포함된 R행 S열 격자 형태의 석유 지도를 만들 수 있었다. 각 칸은 땅 혹은 기름을 의미하며 기름이 포함된 영역은 0 이상 9 이하의 기름이 포함되어 있다. 기름이 포함된 칸은 상, 하, 좌, 우로 연결되어 있다.
우리는 사막에 몇 개의 시추기를 설치하여 기름을 채굴하려고 한다. 시추기는 S개의 열 중 한 곳에 설치할 수 있으며 시추기와 연결된 모든 기름 칸에 있는 기름을 채굴할 수 있다. 여러 개의 시추기와 연결된 기름은 한 번만 채굴된다.
석유 지도의 정보가 주어질 때 시추기를 1 ~ S개 설치했을 때 채굴할 수 있는 최대 기름 양을 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에 R, S가 주어진다. (1 ≤ R, S ≤ 2,000)
두 번째 줄부터 R개의 줄에는 시추할 사막의 정보가 주어진다. ‘.’은 일반 토양, ‘0’~’9’는 기름이 들어있는 영역을 의미한다. 각 수는 해당 칸에 들어있는 기름의 양을 의미한다.
출력
S개의 줄에 걸쳐 답을 출력한다. i번째 줄에는 시추기 i개를 설치했을 때 얻을 수 있는 최대 기름 양을 출력한다.
예제 #1
5 5
...3.
....1
..0.3
489..
.....
21
25
28
28
28
예제 #2
3 5
999.1
.....
1.999
54
56
56
56
56
예제 #3
5 5
.27..
7.063
....7
78...
8...2
48
57
57
57
57
태그
출처
Croatian Highschool Competitions in Informatics 2015 Final Exam 2-2번
로그인해야 코드를 작성할 수 있어요.