N \times N

matrix가 있습니다. 이 때, 좌하단점에서 우상단으로 가는 방법의 수는 몇가지일까요? 단, 같은 점은 2회 방문할 수 없습니다.

예를 들어

2 \times 2

인 matrix는 m[0,0], m[0,1], m[1,0], m[1,1]의 4개 위치가 있습니다. 이 때 출발점은 m[1,0]이고, 도착점은 m[0,1]입니다. 그러면 같은 점을 2회 방문하지 않고 출발점으로부터 도착점으로 가는 방법의 수는

(1) m[1,0] -> m[0,0] -> m[0,1]
(2) m[1,0] -> m[1,1] -> m[0,1]

의 2가지입니다. 즉, 대각선 이동은 안되고 m[1,0]->m[1,1]->m[1,0]->m[0,0]->m[0,1]과 같이 한 점을 2번 방문할 수 없습니다. 이 예의 경우엔 m[1,0]을 2번 방문했으므로 틀린 경우가 됩니다.

단, 반드시 위로 혹은 우측으로만 갈 필요는 없습니다. 예를 들어

3 \times 3

의 matrix의 출발점은 m[2,0]이고 도착점은 m[0,2]입니다. 이 때 m[2,0]->m[1,0]->m[1,1]->m[2,1]->m[2,2]->m[1,2]->m[0,2]와 같은 경로는 가능합니다.