17181번 - 나랏말싸미 America와 different~

토종 한국인 제임스는 외국에서 오래 살아 한글이 약한 김옥순을 위해 한글을 배우는 게임을 만들었다. 게임은 N x M의 표가 주어질 때, (1, 1)좌표에서 출발하여 (N, M) 좌표로 이동하면서 가장 짧은 단어를 만드는 게임이다. 표에서 이동은 상하좌우 4방향으로 가능하다. 이동할 때마다 그 칸에 적힌 자모음을 적고, 적힌 자모음을 순서대로 사용하여 하나의 단어를 만들면 된다.

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

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

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

두 번째 줄부터 N 줄에 걸쳐 표가 한 행씩 입력된다.

표를 통해 만들어지는 가장 짧은 단어의 길이를 출력한다. (N, M) 좌표까지 갈 때 온전한 단어를 만들지 못할 경우 "BAD"를 출력한다.