Problem: Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.  Some of the squares have a lotus leaf on it and cannot be entered. The square (i,j) has a lotus leaf on it if c_{ij} is `@`, and it does not if c_{ij} is `.`.  In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west. The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.  Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2). If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Submission attempts (in order):
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y ==dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            K -= 1
            nx += dx[i]
            ny += dy[i]
        if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[nx][ny] != "@" and depth[nx][ny] > depth[y][x]:
            if depth[ny][nx] == depth[y][x]+1:
                continue
            depth[ny][nx] = depth[y][x] +1
            dq.append((nx,ny))
        else:
            break
print(depth[c][d] if depth[c][d] != float("inf") else -1)




from collections import deque
h,w,k = map(int,input().split())
a,b,c,d=map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
  x,y ==dq.popleft()
  if x == d and y == c:
    break
  for i in range(4):
    nx,ny,K = x,y,k
    while K:
      K -= 1
      nx += dx[i]
      ny += dy[i]
      if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[nx][ny] != "@" and depth[nx][ny] > depth[y][x]:
        if depth[ny][nx] == depth[y][x]+1:
          continue
        depth[ny][nx] = depth[y][x] +1
        dq.append((nx,ny))
      else:
        break
print(depth[c][d] if depth[c][d] != float("inf") else -1)




from collections import deque
h,w,k = map(int,input().split())
a,b,c,d=map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0 1, -1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([b,a])
depth[a][b] = 0
while dq:
  x,y ==dq.popleft()
  if x == d and y == c:
    break
  for i in range(4):
    nx,ny,K = x,y,k
    while K:
      K -= 1
      nx += dx[i]
      ny += dy[i]
      if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[nx][ny] != "@" and depth[nx][ny] > depth[y][x]:
        if depth[ny][nx] == depth[y][x]+1:
          continue
        depth[ny][nx] = depth[y][x] +1
        dq.append((nx,ny))
      else:
        break
print(depth[c][d] if depth[c][d] != float("inf") else -1)




from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
  x,y ==dq.popleft()
  if x == d and y == c:
    break
  for i in range(4):
    nx,ny,K = x,y,k
    while K:
      K -= 1
      nx += dx[i]
      ny += dy[i]
      if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[nx][ny] != "@" and depth[nx][ny] > depth[y][x]:
        if depth[ny][nx] == depth[y][x]+1:
          continue
        depth[ny][nx] = depth[y][x] +1
        dq.append((nx,ny))
      else:
        break
print(depth[c][d] if depth[c][d] != float("inf") else -1)




from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            K -= 1
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                if depth[ny][nx] == depth[y][x]+1:
                    continue
                depth[ny][nx] = depth[y][x] +1
                dq.append((nx,ny))
            else:
                break
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted