問題
떠도는 것을 좋아하는 진우는 어느 날 전설에만 존재하는 줄 알았던 근우조교의 마을에 도착하게 되었다. 이 마을은 특이한 점이 있었는데, 첫 째로 N행 N열의 0이상 3이하의 숫자가 새겨져 있는 정사각형이 붙어있는 형태로 이루어져 있으며, 또한 무조건 동쪽 혹은 남쪽 방향으로만 이동이 가능하다는 것이다. 진우는 아래 그림의 실선으로 그려진 동그라미가 놓여 있는 곳에 서있다. 진우는 점선의 동그라미가 놓여있는 위치에 정현이라는 노래를 잘 부르는 가수가 있다고 하기에 그곳까지 가려고 한다. 편의상 진우의 위치를 (1,1)라고 하고, 정현이가 있는 위치는 (N,N)라고 하자.
하지만 근우조교의 마을은 위에서 이야기한 특이한 점 외에도 또 특이한 점이 있다. 해당 위치에서 다른 곳으로 이동을 하려면 무조건 자신이 서있는 숫자의 칸만큼만 이동이 가능하다. 만약 진우가 위치한 사각형에 0이 있으면 더 이상 아무데도 갈 수 없게 된다. 아래 그림은 마을이 위의 그림처럼 이뤄져 진우가 이동 할 수 있는 모든 경우를 보여준다.
이동 방법이 유일하지 않다는 것을 알게 된 진우는 자신이 정현이에게 가려고 이동할 때 가능한 경우가 몇 가지인지 궁금해졌다. 진우의 궁금증을 해소해주자.
輸入
첫 번째 줄에는 마을의 크기 N(4≤N≤34)가 입력된다. 그 다음 줄부터 N개의 줄에는 N개의 0이상 3이하의 숫자로 이루어진 문자열이 들어오며, X번째 줄의 Y번째 문자는 위의 좌표 (X,Y)에 담긴 숫자를 뜻한다. 입력되는 숫자간의 공백은 존재하지 않음을 유의하자.
輸出
시작점부터 도착점 까지 가는 가능한 방법의 가짓수를 출력한다.
範例
4
2331
1213
1231
3110
3
需要登入才能撰寫程式碼。