2020 CCC J5/Q2 Escape Room (Python) BFS Optimization

Question

Is there a way to optimize my code even further? I am trying to solve the 2020 CCC J5/Q2 question and I have passed all the test cases except for a few, which I am exceeding the time limit.

Link to the question (It is the last question) https://cemc.uwaterloo.ca/contests/computing/2020/ccc/juniorEF.pdf

#definitions
row = int(input())
column = int(input())
array = [list(map(int, input().split())) for x in range(row)]
area = row*column

#Setting the queue to only have -1
pathways = [-1]*(area+1)
emptyS = 0
currentPath = 0
inList = [False] * 1000001

#Setting the first number in the queue to equal the number at [0][0]
pathways[emptyS] = array[0][0]
emptyS += 1`enter code here`
#Checking if the number at [0][0] is the answer (the answer is the area of the array)
if pathways[currentPath] == area:
    print('yes')
    raise SystemExit(0)

#Using BFS to find the answer
#Looping until the queue hits -1
while pathways[currentPath] != -1:
    for x in range(1, row+1):
        if pathways[currentPath] % x == 0:
            for y in range(1, column+1):

#I wasn't sure how to add 1 to every index of my 2d array, so I added 1 in the for loop, and arrayMN is the actual index in my loop.
                arrayMN = array[x-1][y-1]
                if pathways[currentPath] == x*y:

                    #Checking if the value is equal to the answer
                    if arrayMN == area:
                        print("yes")
                        raise SystemExit(0)

                    #If it isn't equal, either replace the -1 in pathways with the number (add it to the queue) or don't add it to prevent a loop)
                    if inList[arrayMN] == False:
                        pathways[emptyS] = arrayMN
                        emptyS += 1
                        inList[arrayMN] = True
    currentPath += 1

#If none of the above works, it is not possible
print('no')

This is my first forum post, so if there are any things I can do to improve my posts, please let me know.

Answer 1

等待大神解答