PCPC12E  Snakes and Ladders
Snakes and Ladders (or Chutes and Ladders) is an ancient Indian board game regarded today as a worldwide classic. It is played between two or more players on a game board having numbered squares (fields) on a grid. A number of "ladders" and "snakes" (or "chutes") are pictured on the board, each connecting two specific board squares. The object of the game is to navigate one's game piece from the start (Bottom square) to the finish (Top Square), helped or hindered by ladders and snakes, respectively. The historic version had root in morality lessons, where a player's progression up the board represented a life journey complicated by virtues (ladders) and vices (snakes). If, after throwing a dice, a player's token lands on the lowernumbered end of a "ladder", the player moves his token up to the ladder's highernumbered square. If he lands on the highernumbered square of a "snake" (or chute), he must move his token down to the snake's lowernumbered square. If any of those cases takes places, we will call a square unstable. Otherwise it is stable.
The game is a simple race contest lacking a skill component, and is popular with young children.
In this problem you’re required to calculate the minimum number of 6sided die throws to move your game piece from the start (bottom square) to the finish (top square).
Formal game description
Fields are arranged on an NxM grid and numbered from 1 to N*M. Last field, indicated by N*M, is referred to as Top Square. Each player starts with a token on a square at position "0" (the imaginary space beside the “1” grid field; Bottom Square), which is always stable. So in total we have N*M+1 fields. In every turn player throws the die and moves up by the given number of squares. If that would result in a field higher than Top Square, then token is not moved. If the square that token ends on is unstable, it is moved as indicated by ladder or snake. This is repeated until token is placed a stable field. You can assume that a stable field can be reached from any field on the board. If this final, stable field is the Top Square, game ends and player wins.
Input Specification
Input contains multiple test cases First line of each test case contains integers N, M, S, L. where n and m are the board dimensions, N (0 < N <= 100), M (0 < M <= 100), and S and L are number of snakes and ladders respectively. Next S lines describes snakes. Each line contains two integers: h and t, where h is the snake’s head position and t is the snake tail position. (0 < t < h <=N*M), Next L lines describes ladders. Each line contains two integers: p and q where p is the ladder’s bottom and q is the ladder’s top (0 < p < q < N*M).
The input will be terminated by the end of file.
NOTE! There could be more snakes and/or ladders leading from a single field. In such a case use the last snake/ladder specified in the input.
Output Specification
Print one line per test case containing the minimum number of dice throws. If you cannot reach to the finish square print 1
Sample Input 1 1 0 0 1 2 1 0 2 1 5 10 3 5 16 6 47 26 49 11 1 38 4 14 9 31 40 42 36 44
Sample Output 1 1 3
See also: Snakes and Ladders Again
hide comments
nadstratosfer:
20180306 09:24:20
Wasted 25mins to figure out how to read the retarded input without NZEC. I guess putting number of cases at the front of the input would be too mainstream, and now that we have to count the goddamn lines we also have to deal with random blanks. This already after zukow had spared us the bonus fun of figuring out WTF the question itself is. Nice problem, but 1 for a frustrating mess of the way it was set. Last edit: 20180306 09:34:23 

kshubham02:
20170925 11:25:38
Can someone please point out error with this approach 


Harish Reddy Kolanu:
20150708 17:30:21
@Rishabh


Rishabh:
20150630 10:10:01
@Harish Any other test cases ? 

Harish Reddy Kolanu:
20150630 03:15:04
finally accepted after many submissions


Rishabh:
20150615 12:56:35
getting WA. Any tricky test cases please ?? 

Aradhya:
20141221 20:39:39
Trolled :D 

:D:
20130323 00:31:42
I made a lot of changes in the description and I hope it is precise now. Please comment / email me in cases something still needs fixing here. "Snakes and Ladders Again" will also be corrected, once I verify it with a solution.

Added by:  abdelkarim 
Date:  20121228 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  The First Palestinian Collegiate Programming Contest 