ZOAC 7

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

요약
Z, O, A, C로 이루어진 N행 M열 격자에서 (1,1)에서 시작해 오른쪽이나 아래로만 이동하고 순간이동을 한 번 사용할 때, 각 문자의 수집 개수의 최댓값을 구한다.
난이도

어려움10점 중 8점

유형
동적 계획법, 누적 합, 배열, 행렬
정답자
아직 제출이 없습니다

문제

Z, O, A, C로만 이루어진 NN행 MM열의 2차원 격자가 있다.

혁준이와 친구들은 11행 11열에서 출발하여 NN행 MM열까지 이동하며 문자들을 수집하려고 한다.

한 번의 이동에 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다.

또한, 현재 칸이 aa행 bb열일 때 딱 한 번 c>ac > a 혹은 d>bd > b를 만족하는 cc행 dd열로 순간이동을 할 수 있다.

다시 말해, 아래 그림의 초록색 칸에서 순간이동하는 경우, 보라색 칸들 중 한 곳으로 이동할 수 있다.

혁준: 나는 Z만 가져올거야!

익준: 그럼 나는 O만 가져올래.

동우: 나는 A만!

진우: 난 C만.

혁준이와 친구들이 각각 가져올 문자들의 최대 개수를 구해보자.

입력

첫 번째 줄에 N,MN, M이 주어진다. (1≤N,M≤2,000)(1 \le N,M \le 2\\,000)

i+1i+1번째 줄에는 격자의 ii행의 원소 MM개가 공백을 사이에 두고 주어진다. (1≤i≤N)(1 \le i \le N)

각 원소는 반드시 Z, O, A, C중 하나이다.

출력

각 문자 Z, O, A, C의 최대 수집 개수를 공백을 사이에 두고 출력한다.

힌트

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.

예제2

  1. 예제 1

    입력
    3 5
Z Z O O A
A C C Z O
A C Z O A
    예상 출력
    4 4 4 3

  2. 예제 2

    입력
    5 6
A Z A C Z C
O C O Z A Z
O Z Z A O A
C Z A Z A C
Z O C O O Z
    예상 출력
    7 6 6 5