Teleportation Tangle

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

qwertytown4life

Problem type

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

The maze can be modelled as an $R$ ~R~ by $C$ ~C~ grid consisting of positive integers, where each integer represents a room. Let $(r, c)$ ~(r, c)~ denote the index of Kevin's current row and column respectively, and let $V$ ~V~ denote the positive integer at $(r, c)$ ~(r, c)~. From any room $(r, c)$ ~(r, c)~, Kevin can teleport exactly $V$ ~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)$ ~(r, c)~, moving to $((r \pm V) \bmod R, c)$ ~((r \pm V) \bmod R, c)~ or $(r, (c \pm V) \bmod C)$ ~(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$ ~R~ and $C$ ~C~ $(1 \le R, C \le 10^3)$ ~(1 \le R, C \le 10^3)~, the number of rows and columns in the maze.

The next $R$ ~R~ lines will contain $C$ ~C~ positive integers in the range, $[1, 10^9]$ ~[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.

Subtasks

Subtask 1 [40%]

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

Subtask 2 [60%]

No additional constraints.

Sample Input 1

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)$ ~(0,1)~. Then, he teleports up four rooms looping around to $(2,1)$ ~(2,1)~. Finally, he teleports left five rooms to loop around and reach $(2,2)$ ~(2,2)~.

Sample Input 2

Sample Output 2

FOREVER

Explanation for Sample Output 2

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

Comments

3

Dingledooper commented on April 29, 2020, 4:57 a.m.

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

3

Josh commented on April 29, 2020, 10:51 a.m.

Grid should be of type int, not char.

3

Dingledooper commented on April 29, 2020, 6:55 p.m.

:facepalm: Thanks for the help.