I recently have been doing some competition problems. In particular this one:

https://open.kattis.com/problems/knightjump

An abridged statement of the problem:

You are given a two dimensional (square) chess board of size N (1-based indexing). Some of the cells on this board are ‘.’ denoting an empty cell. Some of the cells on this board are ‘#’ denoting a blocked cell, which you are not allowed to visit. Exactly one of the cells on this board is ‘K’ denoting the initial position of the knight. Determine the minimum number of steps required for the Knight to reach cell (1,1) while avoiding cells with ‘#’ in the path.

I know this is a simple BFS problem and have written the following code to solve it:

from collections import deque
from sys import stdin

dirs = ((2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2))

N = int(stdin.readline())
q = deque()
mat = [list(str(stdin.readline())) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if mat[i][j] == "K":
            inX, inY = i 1, j 1
            break

q.append((inX,inY,0))
flag = False
visited = [[0]*N for _ in range(N)]
while q:
    ix,iy, moves = q.popleft()
    visited[ix-1][iy-1] = 1
    if (ix,iy) == (1,1):
        print(moves)
        flag = True
        break
    
    for d in dirs:
        dx,dy = d
        if 1 <= ix   dx < N 1 and 1 <= iy   dy < N 1 and mat[ix dx-1][iy dy-1] != "#" and visited[ix dx-1][iy dy-1] == 0:
            q.append((ix dx,iy dy, moves 1))
    
if not flag:
    print(-1)

All test data I've generated has given a correct answer, but I am recieving a time limit error on the site for some cases (and correct on all other). The input limits are N <= 100. I know that C is faster, but I was hoping to use this problem to learn a bit about why my solution times out but many Python solutions on a similar concept perform quick, and hopefully teach me something about Python nuts and bolts I didn't know. For example - I found this solution on someone's Github:

from collections import deque


n = int(input())
grid = [list(input()) for _ in range(n)]
for i in range(n):
    for j in range(n):
        if grid[i][j] == 'K':
            k_i, k_j = i, j
            break
visited = [[0 for x in range(n)] for y in range(n)]

# time complexity is number of configs (n^2) multiplied by
# work per configs (iterate through 8 deltas)
def k_jumps(i, j):
    q = deque()
    q.append((0, i, j))
    visited[i][j] = 1
    valid = False
    while len(q) > 0:
        d, i, j = q.popleft()
        if (i,j) == (0,0):
            print(d)
            valid = True
            break

        deltas = {(-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (2, 1), (2, -1), (-1, -2)} 
        for delta in deltas:
            di, dj = delta
            if 0 <= i   di < n and 0 <= j   dj < n and visited[i di][j dj] == 0 and grid[i di][j dj] != '#':
                visited[i di][j dj] = 1
                q.append((d 1, i di, j dj))
    if not valid:
        print(-1)
            
k_jumps(k_i, k_j)

(Thanks to user Case Pleog).

Superficially the solutions are the same (BFS) - however the second solution runs in 0.07s, while my solutions times out at over 1s.

While there are some minor differences between our solutions, I can't see what explains such a large time discrepancy. I already made some changes to my code to see if that was the issue, e.g. the line:

if 1 <= ix   dx < N 1 and 1 <= iy   dy < N 1 and mat[ix dx-1][iy dy-1] != "#" and visited[ix dx-1][iy dy-1] == 0:

and indeed that speeded things up, as before I was using:

if min(point) > 0 and max(point) < N 1 and mat[point[0] dx-1][point[1] dy-1] != "#" and visited[point[0] dx-1][point[1] dy-1] == 0:

where point was a tuple consisting of ix,iy. Any advice would be appreciated - I would like to know more about what's causing the time difference as its > 10x difference. This is just a hobby, so some of my code may have amateur quirks/inefficiencies which hopefully I can explain. Thanks!

CodePudding user response：

Do visited[ix dx-1][iy dy-1] = 1 right away when you do q.append((ix dx,iy dy, moves 1)), otherwise you might put that same coordinate into the queue multiple times.