시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 164 48 34 26.562%

문제

토종 한국인 제임스는 외국에서 오래 살아 한글이 약한 김옥순을 위해 한글을 알려주려 한다. 외국에서 살아 받침을 잘 알지 못하는 김옥순을 위해 제임스는 한글의 받침에 대해 공부할 수 있는 게임을 만들었다.  게임은 N x M의 표가 주어질 때 (1, 1)좌표에서 출발하여 (N, M) 좌표로 이동했을 때 가장 짧은 글자 수를 찾는 게임이다. 표에서 이동은 상하좌우 4방향으로 가능하다.

N이 5이고 M이 4인 위의 예시를 보면 추매보대추우보대 같은 단어를 만들어 낼 수 있지만 가장 짧은 글자 수는 3개로 충남대가 만들어질 수 있다. 김옥순 씨에게 문제를 내기 위해 게임의 정답이 무엇인지 알아야 하기 때문에 문제를 풀어보아야 한다.  한글 입출력을 원활하게 진행하기 위해 다음 표와 같이 자음과 모음 대신 숫자가 주어진다. 제임스를 도와 게임의 정답을 알아보자.

글자를 만들 때 자음은 쌍자음이나 겹받침으로 이어 붙여서 사용하지 못하며, 문제에서 주어지는 모든 자음은 모든 모음에 대해 초성과 종성으로 사용할 수 있다고 가정한다. 

입력

첫 번째 줄에는 표의 가로와 세로 길이인 NM이 주어진다. (4 ≤ N ≤ 50, 4 ≤ M ≤ 50)

두 번째 줄부터 줄에 걸쳐 표가 한 행씩 입력된다. 표의 각 숫자는 0보다 크거나 같고 34보다 작거나 같다.

출력

표를 통해 만들어지는 가장 짧은 글자 수를 출력한다.

(NM) 좌표까지 갈 때 온전한 글자를 만들지 못할 경우 "BAD"를 출력한다.

예제 입력 1

5 4
9 27 1 6
27 7 1 2
4 27 14 16
15 5 4 20
4 22 2 15

예제 출력 1

3

한글로 입력이 주어졌다면 아래와 입력이 같다.

5 4
ㅊ ㅜ ㄴ ㅅ
ㅜ ㅇ ㄴ ㄷ
ㅁ ㅜ ㅏ ㅑ
ㅐ ㅂ ㅁ ㅕ
ㅁ ㅗ ㄷ ㅐ

정답은 "충남대" 가 된다.

예제 입력 2

5 4
9 27 1 6
27 7 1 2
4 27 14 16
15 5 4 2
4 22 2 2

예제 출력 2

BAD

한글로 입력이 주어졌다면 아래와 입력이 같다.

5 4
ㅊ ㅜ ㄴ ㅅ
ㅜ ㅇ ㄴ ㄷ
ㅁ ㅜ ㅏ ㅑ
ㅐ ㅂ ㅁ ㄷ
ㅁ ㅗ ㄷ ㄷ

단어를 만들 수 없으므로 "BAD"가 된다.