STAR3CAS  THE WEIRD STAIRCASE
You are given a representation of a stair case with 'N' steps (0 to n1). In every step a number x[i] (for ith step) is written on it. At each step you have two choices. Either you can to proceed to next step(i+1) or you can jump x[i] steps from that step(to i+x[i] th step). If the number wriiten on the step is less than 0 , you can come down that many number of steps or climb one step up.
Initially you are standing at the 0th step.
Find the minimum number of jumps needed to reach the top of the stair case.
If there is no way to reach the top of the stair case, print 1 , else print the minimum number of jumps needed to reach the top of the staircase(nth step).
If a jump results in a step , which is greater than n, it is an invalid move.
Input
First line consists of 'T' , the number of test cases . In every test case , the first line consists of 'n' , the number of steps. The next line consists of n integers , x[0] to x[n1] .
Output
Print the minimum number of jumps required to reach the nth step . "Nth Step" is described in the problem statement.
Input Constraints:
1<=T<=1000
1<=n<=20
17<=x[i]<=17 and x[i] != 0
Sample Input:
2
6
1 2 1 3 3 3
10
5 1 1 1 6 1 1 1 1 1
Sample Output:
3
3
hide comments
spoj_mradul:
20200328 21:33:56
Last edit: 20200328 21:34:29 

badboy_1496:
20180719 15:54:48
solved with [spoiler]!!! ac in one go!!! Last edit: 20180822 15:59:33 

nadstratosfer:
20180327 06:38:36
The choice is always i+1, i+x[i], regardless of the value of x[i]. Like cegprakash said, this is not a greedy problem so don't follow 785227's comment; instead figure out what algo he might have confused BFS with. 

jaideeppyne:
20170819 05:36:30
Easy problem with [spoiler]. Take care of negative elements in the array. You need to iterate through the [spoiler] loop as many times as many negative numbers are present in the array.Happy Coding ! :D Last edit: 20180822 16:00:12 

Sigma Kappa:
20170625 11:56:37
Trivial.... should be moved to Tutorial. In place of this, tasks such as SPTTRN13 should be moved from tutorial to the classical. 

Mostafa Ali Mansour:
20160526 20:00:46
My first recursion prblm Last edit: 20160526 20:01:25 

785227:
20140619 12:48:19
My first ever bfs :) 

cegprakash:
20140619 12:48:19
Don't be greedy and take care of cycles. 

pokemon:
20140619 12:48:19
anymore test cases....?


cegprakash:
20140619 12:48:19
check for upper/lower limits 
Added by:  cegprakash 
Date:  20130301 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: BF GOSU 