시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 343 77 70 35.714%

문제

n*n 게임 보드에 양의 숫자들이 적혀있다. 목적은 왼쪽 위에서 오른쪽 아래까지 규칙에 맞게 점프를 해서 가는 것이다. 숫자들은 현재 점에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 갈 수 있으며 0은 더 이상의 진행을 막는 종착점이다. 다시 말해서 현재 점의 숫자만큼 오른쪽이나 아래쪽으로 가야한다는 의미이다.

입력

첫번째 줄에는 양에 정수 N(4 ≤ N ≤ 100)가 들어오고, 그 다음 n개의 줄에 각각 0~9사이의 숫자 n개가 들어온다.

출력

왼쪽 위에서 오른쪽 아래로 위의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 클 수 있으며, 100자리를 넘지는 않는다.

예제 입력

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

예제 출력

3

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: conankun