꿀꿀이 사방치기 timer 1s memory 128MB

올해도 꿀꿀이들을 위한 축제 꿀꿀이 올림피아드 시즌이 되었다. 올해는 살아있는 전설의 꿀꿀이 미스터 Bu가 새로운 종목을 제안하였다. 이름 하여 사방치기!  두둥~~.

사실 사방치기는 새로운 종목은 아니다. 예전부터 있던 종목이었으나 체중이 1톤을 향하여 가고 있는 꿀꿀이들에게 사각형 격자를 이리 저리 뛰어 다니라는 것은 거의 재앙 이어서 그동안 정식 종목에서 제외 되었던 것이었다. 그런데 이제 와서 이 종목을 다시 제안하는 누구보다 무거운 미스터 Bu의 아리송한 발상은 무얼까?

엉뚱 꿀꿀이 앙데용 팝이 개발한 점핑 보조기구 빠빠빠-콩콩이 최근 출시되었기 때문이다. 빠빠빠-콩콩의 탄력은 실로 놀라워서 꿀꿀이를 태우고 사방치기 경기장내의 어느 곳이든 한 번에 점프할 수 있다고 한다.

꿀꿀이 사방치기 경기장은 N개의 행과 M개의 열을 가진 격자 모양이며 각각의 격자는 붉은색(‘R’) 또는 푸른색(‘B’)로 색칠되어 있다.

상단 왼쪽 1행 1열에서 출발하여 하단 오른쪽 N행 M열에 도착하는데 점프할 때는 아래와 같은 규칙을 지켜야 한다.   1) 현재 있는 곳과는 다른 색을 가진 격자로 점프하여야 한다.   2) 아래로 한 행 이상 점프하여야 한다.   3) 오른쪽으로 한 칸 이상 점프하여야 한다. 알다시피 꿀꿀이들의 체격은 상상을 초월하므로 두 마리 이상의 꿀꿀이가 같은 코스를 동시에 점프하며 이동하기는 불가능에 가깝다. 따라서 경기장이 준비되면 서로 다른 경로의 개수를 구하여 출전하는 꿀꿀이의 수를 정한다. 이 경로의 개수를 구하는 임무가 똑똑이 꿀꿀이 당신에게 주어졌다. 실력을 발휘해 보자.