알파벳 경로

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

요약

격자의 왼쪽 위 칸에서 시작해 인접 칸으로만 이동하며 이미 쓴 알파벳을 다시 밟지 않는 경로 중 가장 많은 칸을 방문하는 경우를 구합니다.

문제

세로 $R$ 칸, 가로 $C$ 칸인 보드가 있다. 각 칸에는 대문자 알파벳 한 글자가 적혀 있으며, 말은 왼쪽 위 칸( $1$ 행 $1$ 열)에서 시작한다.

말은 상하좌우로 인접한 칸으로 이동할 수 있다. 단, 이동하려는 칸의 알파벳은 지금까지 지나온 모든 칸의 알파벳과 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 이상 지날 수 없다.

시작 칸을 포함하여 말이 지날 수 있는 최대 칸 수를 구하라.

첫째 줄에 $R$ 과 $C$ 가 공백으로 구분되어 주어진다. ( $1 \le R,C \le 20$ )

둘째 줄부터 $R$ 개의 줄에 걸쳐 보드에 적힌 $C$ 개의 대문자 알파벳이 공백 없이 주어진다.

첫째 줄에 말이 지날 수 있는 최대 칸 수를 출력한다.