PCPC12E - Snakes and Ladders

no tags 

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 lower-numbered end of a "ladder", the player moves his token up to the ladder's higher-numbered square. If he lands on the higher-numbered square of a "snake" (or chute), he must move his token down to the snake's lower-numbered 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 6-sided 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.

PIC

Input

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

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

Output
1
-1
3

See also: Snakes and Ladders Again


hide comments
nadstratosfer: 2018-03-06 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: 2018-03-06 09:34:23
kshubham02: 2017-09-25 11:25:38

Can someone please point out error with this approach -
Consider a graph where each node represents a cell on the board. A node is connected to its next 6 nodes (if they exist) with cost 1 (You need 1 move to reach there). If it is snake's or ladder's starting point, it is also connected with all such nodes which are the snake's or ladder's end point, with cost 0 (You can reach the other end without a move).
In this graph, run Dijkstra.
I am getting WA.

PS : My code runs correctly on both test cases provided by Harish here.

Last edit: 2017-09-25 11:27:41
Harish Reddy Kolanu: 2015-07-08 17:30:21

@Rishabh
1 100 6 0
10 2
11 3
12 4
13 5
14 6
15 7
ans : -1

Last edit: 2015-07-09 03:43:45
Rishabh: 2015-06-30 10:10:01

@Harish Any other test cases ?

Harish Reddy Kolanu: 2015-06-30 03:15:04

finally accepted after many submissions
Test cases are tricky
below are few test cases which will be useful
10 10 0 3
6 66
66 88
88 99
ans : 2

Rishabh: 2015-06-15 12:56:35

getting WA. Any tricky test cases please ??

Aradhya: 2014-12-21 20:39:39

Trolled :D

:D: 2013-03-23 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.

Also regarding one of the now hidden comments: if description isn't precise it needs fixing. For problems like "guess sequence" we have a new Riddle category. An algorithmic problem should never require you to guess anything. What should be calculated, input/output format and restrictions should be crystal clear. Doing otherwise is not "tricky" and just wastes solvers time. We end up trying to interpret a problem in various ways, with no indication witch one would be correct.

Last edit: 2013-03-23 00:32:20

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