Teleportation Tangle

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kevin is trapped in a maze filled with many rooms and needs your help to escape!

The maze can be modelled as an R by C grid consisting of positive integers, where each integer represents a room. Let (r, c) denote the index of Kevin's current row and column respectively, and let V denote the positive integer at (r, c). From any room (r, c), Kevin can teleport exactly V rooms up, down, left, or right. Also, if Kevin reaches a border, he loops around to the other side.

Looping around is defined as, from any room (r, c), moving to ((r \pm V) \bmod R, c) or (r, (c \pm V) \bmod C).

Given that Kevin starts at the top left corner and the exit is at the bottom right corner, print the minimum number of times he needs to teleport to reach the exit. If it is impossible, print FOREVER to signify that Kevin will never escape the maze!

Input Specification

The first line will contain positive integers R and C (1 \le R, C \le 10^3), the number of rows and columns in the maze.

The next R lines will contain C positive integers in the range, [1, 10^{9}].

Output Specification

Print the minimum number of times Kevin needs to teleport to reach the exit. If it is impossible to reach the exit, print FOREVER.


Subtask 1 [40%]

All integers in the input will be in the range [1, 100].

Subtask 2 [60%]

No additional constraints.

Sample Input 1

3 3
2 4 3
1 1 2
6 5 8

Sample Output 1


Explanation for Sample Output 1

There are multiple solutions. In one solution, Kevin teleports left two rooms looping around to (0,1). Then, he teleports up four rooms looping around to (2,1). Finally, he teleports left five rooms to loop around and reach (2,2).

Sample Input 2

3 3
2 5 9
1 9 3
6 3 8

Sample Output 2


Explanation for Sample Output 2

There is no way to get from (0,0) to (2,2), and Kevin will never escape the maze!


  • 3
    Dingledooper  commented on April 29, 2020, 12:57 a.m.

    Can someone check my code? I can't seem to get past Batch #1. I'm probably missing something really obvious.

    • 4
      Josh  commented on April 29, 2020, 6:51 a.m.

      Grid should be of type int, not char.

      • 3
        Dingledooper  commented on April 29, 2020, 2:55 p.m.

        :facepalm: Thanks for the help.