문제
LETTERS 게임은 R행 C열로 이루어진 사각형 보드의 왼쪽 상단에서 출발하여
상, 하, 좌, 우 인접한 셀을 따라 이동하는 게임이다.
각 셀에는 알파벳 대문자가 하나씩 들어있으며 방문할 때 마다 알파벳 대문자를 상품으로 얻는다.
이동규칙은 다음과 같다.
1. 보드의 경계를 벗어날 수 없다.
2. 이미 방문한 곳을 다시 지나갈 수 없다.
3. 이미 획득한 알파벳과 같은 문자가 있는 셀을 방문할 수 없다.
재범이가 LETTERS게임을 하고 있다.
보드판의 정보가 주어질 때 재범이가 얻을 수 있는 최대 알파벳 수를 구하는 프로그램을 작성하시오.
입력
첫 행에 행과 열의 크기를 나타내는 R, C가 공백으로 구분되어주어진다. (1 <= R, C <= 20)
두 번째 행에서부터 R개의 행에 걸쳐 각 행마다 C개의 대문자가 공백없이 주어진다.
출력
규칙에 맞게 이동할 때 얻을 수 있는 최대 알파벳 개수를 출력한다.
예제1
입력
24
CAAB
ADCB
출력
3
예제2
입력
36
HFDFFB
AJHGDH
DGAGEH
출력
6
예제3
입력
55
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH
출력
10
출처
Croatian Highschool Competitions in Informatics / 2002 / Regional Competition - Juniors 3번