로마 숫자 걷기

시간 제한1초메모리 제한128 MB

요약

격자 중심에서 시작해 빈 칸으로 구분된 연속 로마 숫자 1,2,3...을 최대한 길게 찾아 마지막 숫자를 출력하는 문제입니다.

난이도: 어려움10점 중 8점
유형: DFS, 백트래킹, 문자열, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

N x N 정사각형 격자가 주어진다. 각 칸은 비어 있거나 로마 숫자 문자 I, V, X, L, C, D 중 하나를 담고 있다. 이 문자의 값은 각각 1, 5, 10, 50, 100, 500이다.

N은 홀수이고, 가운데 칸은 항상 비어 있다. 가운데 칸에서 시작해 한 번에 위, 아래, 왼쪽, 오른쪽으로 인접한 칸 하나로 이동한다. 가운데 칸을 떠난 뒤 방문한 문자들은 1부터 시작하는 연속된 양의 정수들의 로마 숫자 표기를 차례대로 이루어야 한다. 각 정수의 표기 뒤에는 마지막 정수까지 포함해 구분자 역할을 하는 빈 칸을 정확히 하나 방문해야 한다.

가능한 한 긴 수열을 만드는 것이 목표이다. 그런 수열에 포함될 수 있는 마지막 정수의 최댓값을 출력하라.

10진수를 이 로마 숫자 표기로 바꿀 때는 각 자릿수를 높은 자리부터 낮은 자리 순서로 따로 변환한 뒤 이어 붙인다. 예를 들어 726 = 700 + 20 + 6은 DCCXXVI가 된다. 이 문제에서 사용하는 감산 표기는 IV, IX, XL, XC, CD이며, 따라서 499 = 400 + 90 + 9는 CDXCIX가 된다.

입력

첫째 줄에 홀수인 정수 N (1 <= N <= 99)이 주어진다.

다음 N개 줄에는 정사각형 격자의 한 행을 나타내는 N개의 문자가 주어진다. 각 문자는 I, V, X, L, C, D, . 중 하나이다. 점은 빈 칸을 뜻한다.

출력

만들 수 있는 가장 긴 수열에서 마지막 수를 10진수로 한 줄에 출력한다.

예제3

예제 1
입력
```
3
I.I
I.V
I..
```
예상 출력
```
6
```
예제 2
입력
```
5
.IV.I
II.II
XV.VI
..I..
...II
```
예상 출력
```
11
```

예제 3

입력

7
IIXV.LX
XL.IXVI
.IVIX.X
LIX.VIX
X.XIXI.
LIVL.XX
VI.XIXL

예상 출력