n * m 의 직사각형 그리드(격자 모양으로 되어있는 판)로 된 맵이 있다.

출발점이 왼쪽 아래의 모서리의 점이고, 도착점이 오른쪽 위의 모서리의 점이라 하자.

그리고 이동은 격자의 선을 따라 이동을 할 수 있고, 하나의 단위 사각형( 1 * 1 크기의 사각형)의 변을 지날 때,

그 변을 최소로 하는 경우가 몇 가지인지 알아보는 프로그램을 작성하라.

아래와 같이 4 * 5의 그리드에선 다음과 같이 이동할 경우 거치는 변이 최소가 된다.

굵은 표시가 이동 경로를 뜻한다.

Paths on a grid timer 1s memory 64MB

Paths on a grid 1s 64MB