프로그램 명: boi_jump
제한시간: 1 초
어느 n × n 게임판에는 각 셀마다 음이 아닌 정수가 들어가 있다.
이 게임의 승리 목표는 정당하게 "왼쪽 위 코너"에서 "오른쪽 아래 코너"까지 점프를 하는 것이다.
한 셀에 있는 정수는 반드시 해당 정수만큼 뛰도록 지시한다.
만약 특정 방향에 대하여 점프 크기가 게임 판을 벗어날 것 같다면, 이 방향으로 뛰는 것을 금지한다.
모든 점프는 오른쪽 또는 아랫쪽 방향으로만 뛰어야한다.
만약 셀의 숫자가 0이라면, 더 이상 뛸 수 없다는 것에 주의하라.
아래 보이는 Figure 1을 고려해보면, 실선으로 표시된 원은 시작점이고, 점선으로 표시된 원은 도착점이다.
Figure 2는 시작점에서 도착점으로 갈 수 있는 세 가지 정당한 경로이다. 불필요한 숫자들은 지웠다.
당신이 해야할 일은 "왼쪽 위 코너"에서 "오른쪽 아래 코너"로 뛸 수 있는 정당한 경로의 수를 구하는 것이다.
입력
-
첫번째 줄에는 보드판의 크기인 n이 입력된다. (4 <=n <=100)
-
이 후 n개의 줄에 걸쳐서 0~9 범위의 정수가 n개씩 입력된다.
출력
"왼쪽 위 코너"에서 "오른쪽 아래 코너"로 갈 수 있는 정당한 경로의 수를 출력한다.
An n × n game board is populated with integers, one nonnegative integer per square.
The goal is to jump along any legitimate path from the upper left corner to the lower
right corner of the board. The integer in any one square dictates how large a step away
from that location must be. If the step size would advance travel off the game board,
then a step in that particular direction is forbidden. All steps must be either to the right
or toward the bottom. Note that a 0 is a dead end which prevents any further progress.
Consider the 4 × 4 board shown in Figure 1, where the solid circle identifies the start
position and the dashed circle identifies the target. Figure 2 shows the three legitimate
paths from the start to the target, with the irrelevant numbers in each removed.
Your task is to write a program that determines the number oflegitimate paths
from the upper left corner to the lower right corner.
입력
The input contains a first line with a single postive integer n , 4 <=n <=100,
which is the number of rows in this board. This is followed by n rows of data.
Each row contains n integers , each one from the range 0..9.
출력
The output should consist of a single line containing a single integer, which is the number of legitimate paths from the upper left corner to the lower right corner.
입출력 예
입력
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0
출력
3
출처:boi 2006
번역:Fate
[질/답]
[제출 현황]
[푼 후(1)]