CCC ’20 S2 – Escape Room

For a Junior 5 question, Escape Room isn’t that easy. The brute-force method would be to use breadth first search and find factors, but that will almost guarantee the time will exceed the limit. To solve this, we will need to use a method that doesn’t require any calculations involving factors.

To solve this, we can make a table. The top numbers are labeled 1-rows*columns. Then, for each number, the x-coordinates * the y-coordinates is the number they go to. For example, take the room below:

3, since it’s on coordinates 1×1, it will go to under 1. 10 will go under 2, since it’s 1×2. It goes on to 9, which will go under 12. This will create the table below:

Then, we start at 1. The number below it is 3. So it goes to the third section. There is a list of [8, 6]. For every term i, it checks the ith term. If the term being checked, is rows*columns, then the answer is yes. If rows*columns could never be reached, then the answer is no. To prevent infinite loops, there will be a checklist, that doesn’t check a number if it has already been checked.

In the example, 1 goes to 3. In the 3rd term, it starts by going to 8. In the 8th term, there is 12. 12 = 3*4, so the answer is yes.

Sample solution:

from sys import exit, setrecursionlimit, stdin
setrecursionlimit(1000000)
input = stdin.readline


def check(p):
    if p == rows*columns:
        print('yes')
        exit(0)
    if not checklist[p-1]:
        checklist[p - 1] = True
        for j in second[p-1]:
            if j > rows*columns:
                continue
            check(j)



rows, columns = int(input()), int(input())
second = [[] for i in range(rows*columns)]
checklist = [False for i in range(rows*columns)]
for x in range(1, rows+1):
    i = input().split()
    for y in range(1, columns+1):
        second[x*y-1].append(int(i[y-1]))
i = second[0][0]
if i <= rows*columns:
    check(i)
print('no')

Note: This program uses recursion. For very big rooms, there will be recursion errors. To prevent this, set the recursion limit to a very high number.