ICPC에서 좋은 성적을 얻으려면 수행을 빠뜨릴 수 없습니다. 토끼는 ICPC 우승을 위해 오늘도 수행을 합니다.
오늘의 수행은 유행하는 퍼즐을 재빨리 풀어 순발력을 기르는 것입니다. 오늘 도전할 퍼즐은 여러 색깔의 타일을 솜씨 좋게 없애는 것입니다.
초기 상태로 격자 위에 몇몇 칸에 타일이 놓여 있습니다. 각 타일은 색이 있습니다. 플레이어는 게임 시작 후, 아래의 순서대로 몇 번이고 조작을 수행할 수 있습니다.
1. 타일이 놓여있지 않은 칸을 하나 선택합니다.
2. 선택한 칸에서 시작해 위로 이동하며 살펴보다가 타일이 놓여있는 칸에 다다르면 그 타일을 주목합니다. 타일이 놓여있는 칸을 찾지 못한 채 격자 끝에 다다른다면 어떤 칸에도 주목하지 않습니다.
3. 선택한 칸을 기준으로 같은 조작을 아래, 왼쪽, 오른쪽으로도 수행합니다. 최대 4장의 타일을 주목하게 됩니다.
4. 주목한 타일 중 같은 색이 있으면 그 타일을 격자에서 제거합니다. 같은 색 타일이 두 개라면 둘 다 제거합니다.
5. 제거한 타일의 개수만큼 점수를 얻습니다.
6. 주목을 해제합니다.
예를 들어, 아래의 상황을 생각해봅시다. 타일이 놓이지 않은 칸은 온점으로, 타일의 색은 알파벳으로 표시했습니다.
(그림 참조)
위에서부터 2번째 줄, 왼쪽에서부터 3번째 칸을 선택한 조작을 생각해봅시다. 주목하게 되는 타일은 A, B, B 3개이므로, B 2장이 사라지고 격자는 아래와 같이 바뀌며 2점을 득점하게 됩니다.
(그림 참조)
이 퍼즐은 여유를 부리면 시간 초과로 격자의 일부가 보이지 않게 돼 수행이 얼마나 부족했는지가 알 수 없게 됩니다. 색마다 타일은 2장씩 놓여있지만, 전부 없앨 수 있다고는 장담할 수 없으므로 미리 득점의 최대치를 프로그램에 계산해 두려 합니다.
입력
(형식 참조)
정수 M, N이 격자가 세로 M X 가로 N개 칸으로 이루어져 있음을 나타냅니다. Ci,j는 알파벳 대문자 또는 온점(.)입니다. 위에서부터 i번째 줄이자 왼쪽에서부터 j번째 줄에 해당하는 칸을 나타내는데, 알파벳 대문자일 경우 놓여있는 타일의 색을 의미하며 온점일 경우 칸에 타일이 놓여있지 않음을 나타냅니다.
1 <= M <= 500, 1 <= N <= 500입니다. 각 알파벳 대문자는 입력에서 0번 또는 2번 등장합니다.
ez_code 3년 전 1
문제
ICPC에서 좋은 성적을 얻으려면 수행을 빠뜨릴 수 없습니다. 토끼는 ICPC 우승을 위해 오늘도 수행을 합니다.
오늘의 수행은 유행하는 퍼즐을 재빨리 풀어 순발력을 기르는 것입니다. 오늘 도전할 퍼즐은 여러 색깔의 타일을 솜씨 좋게 없애는 것입니다.
초기 상태로 격자 위에 몇몇 칸에 타일이 놓여 있습니다. 각 타일은 색이 있습니다. 플레이어는 게임 시작 후, 아래의 순서대로 몇 번이고 조작을 수행할 수 있습니다.
1. 타일이 놓여있지 않은 칸을 하나 선택합니다.
2. 선택한 칸에서 시작해 위로 이동하며 살펴보다가 타일이 놓여있는 칸에 다다르면 그 타일을 주목합니다. 타일이 놓여있는 칸을 찾지 못한 채 격자 끝에 다다른다면 어떤 칸에도 주목하지 않습니다.
3. 선택한 칸을 기준으로 같은 조작을 아래, 왼쪽, 오른쪽으로도 수행합니다. 최대 4장의 타일을 주목하게 됩니다.
4. 주목한 타일 중 같은 색이 있으면 그 타일을 격자에서 제거합니다. 같은 색 타일이 두 개라면 둘 다 제거합니다.
5. 제거한 타일의 개수만큼 점수를 얻습니다.
6. 주목을 해제합니다.
예를 들어, 아래의 상황을 생각해봅시다. 타일이 놓이지 않은 칸은 온점으로, 타일의 색은 알파벳으로 표시했습니다.
(그림 참조)
위에서부터 2번째 줄, 왼쪽에서부터 3번째 칸을 선택한 조작을 생각해봅시다. 주목하게 되는 타일은 A, B, B 3개이므로, B 2장이 사라지고 격자는 아래와 같이 바뀌며 2점을 득점하게 됩니다.
(그림 참조)
이 퍼즐은 여유를 부리면 시간 초과로 격자의 일부가 보이지 않게 돼 수행이 얼마나 부족했는지가 알 수 없게 됩니다. 색마다 타일은 2장씩 놓여있지만, 전부 없앨 수 있다고는 장담할 수 없으므로 미리 득점의 최대치를 프로그램에 계산해 두려 합니다.
입력
(형식 참조)
정수 M, N이 격자가 세로 M X 가로 N개 칸으로 이루어져 있음을 나타냅니다. Ci,j는 알파벳 대문자 또는 온점(.)입니다. 위에서부터 i번째 줄이자 왼쪽에서부터 j번째 줄에 해당하는 칸을 나타내는데, 알파벳 대문자일 경우 놓여있는 타일의 색을 의미하며 온점일 경우 칸에 타일이 놓여있지 않음을 나타냅니다.
1 <= M <= 500, 1 <= N <= 500입니다. 각 알파벳 대문자는 입력에서 0번 또는 2번 등장합니다.
출력
득점의 최대치를 한 줄에 출력합시다.