Problem:


Score : 600 points

Problem Statement

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.

Constraints

1 \leq H,W,K \leq 10^6

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}

Output

Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print -1 if the travel is impossible.

Sample Input 1

3 5 2
3 2 3 4
.....
.@..@
..@..

Sample Output 1

5

Initially, Snuke is at the square (3,2).
He can reach the square (3, 4) by making five strokes as follows:

From (3, 2), go west one square to (3, 1).

From (3, 1), go north two squares to (1, 1).

From (1, 1), go east two squares to (1, 3).

From (1, 3), go east one square to (1, 4).

From (1, 4), go south two squares to (3, 4).

Sample Input 2

1 6 4
1 1 1 6
......

Sample Output 2

2

Sample Input 3

3 3 1
2 1 2 3
.@.
.@.
.@.

Sample Output 3

-1



Sample input:
3 5 2
3 2 3 4
.....
.@..@
..@..


Sample output:
5

Submission status: Runtime Error

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]

from collections import deque
sys.setrecursionlimit(10**6)
h,w,k=NM()
x1,y1,x2,y2=NM()
l=[[1]*(w+2)]+[[1]+[1 if j=="@" else 0 for j in input()]+[1] for i in range(h)]+[[1]*(w+2)]
ans=[[-1]*(w+2) for i in range(h+2)]
def dfs(x,y,d,muki,p):
    if ans[x][y]!=-1 or l[x][y]==1:
        return 
    ans[x][y]=d
    q.append((x,y))
    if p>0:
        dx,dy=muki
        dfs(x+dx,y+dy,d,muki,p-1):

q=deque([(x1,y1)])
ans[x1][y1]=0
while q:
    x,y=q.popleft()
    d=ans[x][y]
    dfs(x+1,y,d+1,(1,0),k-1)
    dfs(x-1,y,d+1,(-1,0),k-1)
    dfs(x,y+1,d+1,(0,1),k-1)
    dfs(x,y-1,d+1,(0,-1),k-1)

print(ans[x2][y2])

Submission status: Runtime Error

Solution code:
#G
import pprint
H,W,K=map(int,input().split())
import copy
x1,y1,x2,y2=map(int,input().split())
#raw=["#"]+["."]*(601)+["#"]
lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])

field.append(lastraw)

#print(field)

goal_point=(y2,x2)

[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]

field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0

while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  #pprint.pprint(field)
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.' or field[tx][ty] ==moves:
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
      elif field[tx][ty] ==moves:
        #field[tx][ty] = moves
        #queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            #field[tx][ty] = moves
            #queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break
#pprint.pprint(field)
print(moves)

Submission status: Runtime Error

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1 and cord[y][x+i] == '.':
                l.append((x+i,y))
            elif cord[y][x+i] == '@':
                f1 = False
            if f2 and cord[y][x-i] == '.':
                l.append((x-i,y))
            elif cord[y][x-i] == '@':
                f2 = False
            if f3 and cord[y+i][x] == '.':
                l.append((x,y+i))
            elif cord[y+i][x] == '@':
                f3 = False
            if f4 and cord[y-i][x] == '.':
                l.append((x,y-i))
            elif cord[y-i][x] == '@':
                f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = '#'
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
print(bfs(xg,yg))

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

dd = [(1,0),(-1,0),(0,1),(0,-1)]
def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = deque([(y,x,-1)])
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    ri = [[0]*w for i in range(h)]
    le = [[0]*w for i in range(h)]
    do = [[0]*w for i in range(h)]
    up = [[0]*w for i in range(h)]

    for i in range(h):
        ri[i][-1] = 0
        for j in range(w-1)[::-1]:
            if c[i][j+1] == "@":
                ri[i][j] = 0
            else:
                l = ri[i][j+1]
                if l < k:
                    ri[i][j] = l+1
                else:
                    ri[i][j] = k
    for i in range(h):
        le[i][0] = 0
        for j in range(1,w):
            if c[i][j-1] == "@":
                le[i][j] = 0
            else:
                l = le[i][j-1]
                if l < k:
                    le[i][j] = l+1
                else:
                    le[i][j] = k

    for j in range(w):
        do[-1][j] = 0
        for i in range(h-1)[::-1]:
            if c[i+1][j] == "@":
                do[i][j] = 0
            else:
                l = do[i+1][j]
                if l < k:
                    do[i][j] = l+1
                else:
                    do[i][j] = k
    for j in range(w):
        up[0][j] = 0
        for i in range(1,h):
            if c[i-1][j] == "@":
                up[i][j] = 0
            else:
                l = up[i-1][j]
                if l < k:
                    up[i][j] = l+1
                else:
                    up[i][j] = k
    while q:
        y,x,p = q.popleft()
        nd = d[y][x] + 1
        for i in range(4):
            if i == 0:
                dy,dx = -up[y][x],0
            elif i == 1:
                dy,dx = do[y][x],0
            elif i == 2:
                dy,dx = 0,-le[y][x]
            else:
                dy,dx = 0,ri[y][x]
            ny,nx = y+dy,x+dx
            if (y,x) == (ny,nx):
                continue
            if nd < d[ny][nx]:
                d[ny][nx] = nd
                q.append((ny,nx,i))
        if p >= 0:
            dy,dx = dd[p]
            ny,nx = y+dy,x+dx
            nd = d[y][x]
            if nd < d[ny][nx]:
                d[ny][nx] = nd
                q.appendleft((ny,nx,p))
    ans = d[s][t]
    if ans < float("inf"):
        print(ans)
    else:
        print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]

from collections import deque
h,w,k=NM()
x1,y1,x2,y2=NM()
l=[[1]*(w+2)]+[[1]+[1 if j=="@" else 0 for j in input()]+[1] for i in range(h)]+[[1]*(w+2)]
ans=[[-1]*(w+2) for i in range(h+2)]
def dfs(x,y,d,muki,p):
    if ans[x][y]!=-1 or l[x][y]==1:
        return 1
    ans[x][y]=d
    if p>0:
        dx,dy=muki
        if dfs(x+dx,y+dy,d,muki,p-1):
            q.append((x,y))
    else:
        q.append((x,y))
    return 0
        
q=deque([(x1,y1)])
ans[x1][y1]=0
while q:
    x,y=q.popleft()
    d=ans[x][y]
    dfs(x+1,y,d+1,(1,0),k-1)
    dfs(x-1,y,d+1,(-1,0),k-1)
    dfs(x,y+1,d+1,(0,1),k-1)
    dfs(1,y-1,d+1,(0,-1),k-1)

print(ans[x2][y2])

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

l=[[] for _ in range(200200)]

def main():
  h,w,k=LI()
  x1,y1,x2,y2=LI()
  field=[S() for _ in range(h)]

  visit=[[False]*w for _ in range(h)]

  q=collections.deque()
  q.append((x1,y1,0))
  # q.popleft()
  while q:
    x,y,c=q.popleft()
    if visit[y][x]:
      continue

    visit[y][x]=True

    for dy,dx in dd:
      for i in range(1,k+1):
        dx*=i
        dy*=i

        ny=y+dy
        nx=x+dx

        if 0<=ny<h and 0<=nx<w:
          if field[ny][nx]=='.':
            q.append((nx,ny,c+1))
            if ny==y2-1 and nx==x2-1:
              return c+1
          else:
            break
        else:
          break

    return -1

# main()
print(main())

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
c=[list(input()) for _ in range(h)]
x1=x1-1
y1=y1-1
x2=x2-1
y2=y2-1

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]

from collections import deque

d=[[-1]*w for _ in range(h)]
queue=deque()
queue.append((x1,y1))
d[x1][y1]=0
while queue:
    y,x=queue.popleft()
    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        cnt_k=0
        while cnt_k<k:
            if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
                break
            if c[new_y][new_x]=='.' and (d[new_y][new_x]==-1 or d[new_y][new_x]==d[y][x]+1):
                d[new_y][new_x]=d[y][x]+1
                new_y=new_y+d_y
                new_x=new_x+d_x
                queue.append((new_y, new_x))
                cnt_k+=1
            elif c[new_y][new_x]=='.' and d[new_y][new_x]==-1:
                d[new_y][new_x]=d[y][x]+1
                # queue.append((new_y, new_x))
                new_y=new_y+d_y
                new_x=new_x+d_x
                cnt_k+=1
            else:
                break

print(d[x2][y2])

Submission status: Runtime Error

Solution code:
import queue
import sys
input = sys.stdin.readline
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = ""
for i in range(h):
  ci = str(input())
  c += ci
d = [float("inf") for _ in range(w*h)]
q = queue.Queue()
q.put(sx*10**6+sy)
d[w*sx+sy] = 0
while not q.empty():
  pp = q.get()
  nx = pp//10**6
  ny = pp%10**6
  p = d[w*nx+ny]
  for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
    ax = nx + i
    ay = ny + j
    kc = 1
    while  c[w*ax+ay]=="." and kc <= k and ax >=0 and ax < h and ay >=0 and ay < w  and d[w*ax+ay] > p:
      if ax == gx and ay == gy:
        print(p+1)
        exit()
      if d[w*ax+ay] != p:
        d[w*ax+ay] = p+1
        q.put(ax*10**6+ay)
      kc += 1
      ax += i
      ay += j
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
G=[["@"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["@"]+list(input())+["@"]
V=[[10**10]*(w+2) for i in range(h+2)]
V[sy][sx]=0
D=[[[0,0] for j in range(w+2)] for i in range(h+2)]
D[sy][sx]=[1,1]
X=deque([])
Y=deque([])
i=1
while G[sy-i][sx]==".":
  Y.append(sy-i)
  X.append(sx)
  V[sy-i][sx]=1
  D[sy-i][sx][0]=1
  if i==k:
    D[sy-i][sx][0]=0
    break
  i=i+1
i=1
while G[sy+i][sx]==".":
  Y.append(sy+i)
  X.append(sx)
  V[sy+i][sx]=1
  D[sy+i][sx][0]=1
  if i==k:
    D[sy+i][sx][0]=0
    break
  i=i+1

i=1
while G[sy][sx-i]==".":
  Y.append(sy)
  X.append(sx-i)
  V[sy][sx-i]=1
  D[sy][sx-i][1]=1
  if i==k:
    D[sy][sx-i][0]=0
    break
  i=i+1
i=1
while G[sy][sx+i]==".":
  Y.append(sy)
  X.append(sx+i)
  V[sy][sx+i]=1
  D[sy][sx+i][1]=1
  if i==k:
    D[sy][sx-i][0]=0
    break
  i=i+1

while len(X)>0:
  print(X)
  print(Y)
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  if D[y][x]==[0,0]:
    X.append(x)
    Y.append(y)
  if D[y][x]==[1,1]:
    continue
  if D[y][x][1]==0:
    i=1
    D[y][x]=[1,1]
    while G[y][x-i]==".":
      D[y][x-i][1]=1
      if D[y][x-i][0]==0:
        Y.append(y)
        X.append(x-i)
      V[y][x-i]=min(V[y][x-i],V[y][x]+1)
      if i==k:
        D[y][x-i][0]=0
        break
      i=i+1
    i=1
    while G[y][x+i]==".":
      D[y][x+i][1]=1
      if D[y][x+i][0]==0:
        Y.append(y)
        X.append(x+i)
      V[y][x+i]=min(V[y][x+i],V[y][x]+1)
      if i==k:
        D[y][x+i][0]=0
        break
      i=i+1
  if D[y][x][0]==0:
    i=1
    D[y][x]=[1,1]
    while G[y-i][x]==".":
      D[y-i][x][0]=1
      if D[y-i][x][1]==0:
        Y.append(y-i)
        X.append(x)
      V[y-i][x]=min(V[y-i][x],V[y][x]+1)
      if i==k:
        D[y-i][x][0]=0
        break
      i=i+1
    i=1
    while G[y+i][x]==".":
      D[y+i][x][0]=1
      if D[y+i][x][1]==0:
        Y.append(y+i)
        X.append(x)
      V[y+i][x]=min(V[y+i][x],V[y][x]+1)
      if i==k:
        D[y+1][x][0]=0
        break
      i=i+1
if V[gy][gx]==10**10:
  print(-1)
else:
  print(V[gy][gx])
print(V)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
                      
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

def dfs(x,y,kk,d,a):
  #print(kk,d)
  if c[x][y] == '.':
    c[x][y] = a
  else:
    c[x][y] = min(c[x][y],a)
  for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
    if 0 <= x+dx < h and 0 <= y+dy < w and (c[x+dx][y+dy] == '.' or (c[x+dx][y+dy] != '@' and c[x+dx][y+dy] > a)):
      if kk == -1:
        kk = k-1
        a = 1
      elif kk == 0 or d != (dx,dy):
        kk = k
        a += 1
      else:
        kk -= 1
      dfs(x+dx,y+dy,kk,(dx,dy),a)

q = [(0,x1-1,y1-1,-1,())]
while(q):
  qq = []
  for a,x,y,kk,d in q:
    #print(x,y,c[x][y])
    if c[x][y] == '.':
      c[x][y] = a
    else:
      c[x][y] = min(c[x][y],a)
    for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
      if 0 <= x+dx < h and 0 <= y+dy < w and (c[x+dx][y+dy] == '.' or (c[x+dx][y+dy] != '@' and c[x+dx][y+dy]>a):
        if kk == -1:
          kk = k-1
          a = 1
        elif kk == 0 or d != (dx,dy):
          kk = k
          a += 1
        else:
          kk -= 1
        qq.append((a,x+dx,y+dy,kk,(dx,dy)))
  q = qq[:]
  q.sort()

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
print(c)

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict

H,W,K = map(int,input().split())


x,y, z, w = map(int, input().split())
start = (x-1,y-1)                       # スタート地点
goal = (z-1,w-1)                        # ゴール地点

grid = defaultdict()
for j in range(H):
    temp = input()
    for i in range(W):
        grid[(i,j)] = temp[i]

move = []
for i in range(1, K + 1):
    move.append((i,0))
    move.append((-i,0))
    move.append((0,i))
    move.append((0,-i))

visit = set(start)                           # 訪れたかどうかをメモ
next_set = deque()                          # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
next_set.append((start, 0))                 # スタート地点を決める。第二成分は時刻を表す。

# 頂点番号をデクリメントするのを忘れないように

while next_set:                             # p = [] になったら止める
    p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
    for dp in move:                       # 頂点 p から進める経路の候補から一つ選ぶ
        dx, dy = dp
        q = (x + dx, y + dy)
        if q[0]<0 or q[0]>W or q[1] < 0 or q[1] > H:
            print(q)
            continue
        if q == goal:                          # ゴールがあるならば、ここで判定
            print(t + 1)                    # 経路の長さは t + 1 で与えられる
            exit()
        if grid[q] == "@":
            continue
        if q not in visit:                    # 訪れた事がない場所のみ進む。壁などの条件がある場合は、ここに " grid[p] != 壁 " 等を追加する
            visit.add(q)                # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))     # p から q へと移動。時刻を 1 進める
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs():

    d = [[float("inf")] * w for _ in range(h)]
    rule = [[[]] * w for _ in range(h)]
    print(rule[2][4])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    sx = x1 - 1
    sy = y1 - 1
    gx = x2 - 1
    gy = y2 - 1

    que = deque([])
    bl = False
    que.append((sx, sy, -1, 0, bl))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break

        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if p[2] == i:
                if p[3] == k - 1:
                    ok = 0
                    bl = False
                else:
                    ok = p[3] + 1
                    bl = True
            else:
                ok = 0
                bl = False

            if 0 <= nx < h and 0 <= ny < w:
                if data[nx][ny] != "@" and d[nx][ny] == float("inf"):
                    que.append((nx, ny, i, ok, bl))
                    rule[nx][ny].append((i, ok))
                    if bl:
                        d[nx][ny] = d[p[0]][p[1]]
                    else:
                        d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
data = [list(input()) for i in range(h)]

print(bfs())

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from collections import deque

def main():
	h,w,k=MI()
	x1,y1,x2,y2=MI()
	G=["@"]*(w+2)
	for _ in range(h):
		G.append("@")
		G+=(list(map(str,input().rstrip())))
		G.append("@")
	G+=["@"]*(w+2)
	#print(G)


	G[x1*(w+2)+y1]=0
	#print(G)

	Q=deque()
	Q.append((x1*(w+2)+y1,0))

	while Q:
		#print(Q)
		now,d=Q.popleft()
		#print(Q)
		for i in range(1,k+1):
			if G[now+i]==d or G[now+i]=="@":
				break
			elif G[now+i]==".":
				G[now+i]=d+1
				Q.append([now+i,d+1])
			elif G[now+i]>d:
				G[now+i]=d+1
				Q.append([now+i,d+1])


		for i in range(1,k+1):
			if G[now-i]==d or G[now+i]=="@":
				break
			elif G[now-i]==".":
				G[now-i]=d+1
				Q.append([now-i,d+1])
			elif G[now-i]>d:
				G[now-i]=d+1
				Q.append([now-i,d+1])
			else:
				break

		for i in range(1,k+1):
			if G[now+(w+2)*i]==d or G[now+(w+2)*i]=="@":
				break
			elif G[now+(w+2)*i]==".":
				G[now+(w+2)*i]=d+1
				Q.append([now+(w+2)*i,d+1])
			elif G[now+(w+2)*i]>d:
				G[now+(w+2)*i]=d+1
				Q.append([now+(w+2)*i,d+1])
			else:
				break


		for i in range(1,k+1):
			if G[now-(w+2)*i]==d or G[now-(w+2)*i]=="@":
				break
			elif G[now-(w+2)*i]==".":
				G[now-(w+2)*i]=d+1
				Q.append([now-(w+2)*i,d+1])
			elif G[now-(w+2)*i]>d:
				G[now-(w+2)*i]=d+1
				Q.append([now-(w+2)*i,d+1])
			else:
				break
		#print(Q)
	#print(G)

	if G[x2*(w+2)+y2]==".":
		print(-1)
	else:
		print(G[x2*(w+2)+y2])


if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
# F - Pond Skater
from collections import deque
INF = 10**10
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = [[] for _ in range(H+1)]
d = [[-1]*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    c[i] = '.' + input()
d[x1][y1] = 0
que = deque([[x1,y1]])
ans = -1
judge = 1
while len(que)>0:
    if judge==0
        break
    x,y = que.popleft()
    for k in range(1,INF):
        i = x-k
        if judge==0 or i<1 or c[i][y]!='.':
            break
        if d[i][y]<0:
            d[i][y] = d[x][y]+(k-1)//K+1
            if (i,y)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([i,y])
    for k in range(1,INF):
        i = x+k
        if judge==0 or i>H or c[i][y]!='.':
            break
        if d[i][y]<0:
            d[i][y] = d[x][y]+(k-1)//K+1
            if (i,y)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([i,y])
    for k in range(1,INF):
        j = y-k
        if judge==0 or j<1 or c[x][j]!='.':
            break
        if d[x][j]<0:
            d[x][j] = d[x][y]+(k-1)//K+1
            if (x,j)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([x,j])
    for k in range(1,INF):
        j = y+k
        if judge==0 or j>W or c[x][j]!='.':
            break
        if d[x][j]<0:
            d[x][j] = d[x][y]+(k-1)//K+1
            if (x,j)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([x,j])
print(ans)

Submission status: Runtime Error

Solution code:
def LI():return list(map(int,input().split()))

INF=float("inf")
# from pprint import*
from collections import deque

def main():
    MM=10**6
    h,w,k=LI()
    x1,y1,x2,y2=LI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    maze=[None]*(h*MM+w)
    for i in range(h):
        tmp=list(input())
        for j in range(w):
            maze[i*MM+j]=tmp[j]
    # maze=[list(input()) for _ in range(h)]
    
    # dist=[[INF]*(w) for _ in range(h)]
    dist=[INF]*(h*MM+w)
    q=deque([])
    
    q.append((x1*MM+y1))
    dist[x1*MM+y1]=0
    while q:
        iii=q.popleft()
        xn,yn=divmod(iii,MM)
        # (xn,yn)=q.popleft()
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,-kk)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx*MM+yy]=="@":flg=False;break
                if dist[xx*MM+yy]!=INF:continue
                dist[xx*MM+yy]=dist[xn*MM+yn]+1
                q.append((xx*MM+yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,+kk)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx*MM+yy]=="@":flg=False;break
                if dist[xx*MM+yy]!=INF:continue
                dist[xx*MM+yy]=dist[xn*MM+yn]+1
                q.append((xx*MM+yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx*MM+yy]=="@":flg=False;break
                if dist[xx*MM+yy]!=INF:continue
                dist[xx*MM+yy]=dist[xn*MM+yn]+1
                q.append((xx*MM+yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(-kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx*MM+yy]=="@":flg=False;break
                if dist[xx*MM+yy]!=INF:continue
                dist[xx*MM+yy]=dist[xn*MM+yn]+1
                q.append((xx*MM+yy))
        
        
        
        
    # pprint(maze)
    # for j in dist:print(*j)
    ans=dist[x2*MM+y2]
    if ans==INF:
        ans=-1
    print(ans)  
    
main()

Submission status: Runtime Error

Solution code:
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  sx-=1
  sy-=1
  tx-=1
  ty-=1
  calc=lambda x,y:x*1000007+y
  b=[]
  for i in range(h):
    s=input()
    bb=[]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    b.append(bb)
  from collections import deque
  d=deque()
  d.append(calc(sx,sy))
  s=set()
  while d:
    x,y=divmod(d.popleft(),1000000)
    if calc(x,y)in s:
      s.discard(calc(x,y))
      continue
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if x-i<0:break
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append(calc(x-i,y))
      if b[x-i][y]!=0:
        s.add(calc(x-i,y))
      b[x-i][y]=b[x][y]+1
    for i in range(1,k+1):
      if x+i==h:break
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append(calc(x+i,y))
      if b[x+i][y]!=0:
        s.add(calc(x+i,y))
      b[x+i][y]=b[x][y]+1
    for j in range(1,k+1):
      if y-j<0:break
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append(calc(x,y-j))
      if b[x][y-j]!=0:
        s.add(calc(x,y-j))
      b[x][y-j]=b[x][y]+1
    for j in range(1,k+1):
      if y+j==w:break
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append(calc(x,y+j))
      if b[x][y+j]!=0:
        s.add(calc(x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
def LI():return list(map(int,input().split()))

INF=float("inf")
# from pprint import*
from collections import deque

def main():
    MM=10**7
    h,w,k=LI()
    x1,y1,x2,y2=LI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    maze=[list(input()) for _ in range(h)]
    
    # dist=[[INF]*(w) for _ in range(h)]
    dist=[INF]*(h*MM+w)
    q=deque([])
    
    q.append((x1*MM+y1))
    dist[x1*MM+y1]=0
    while q:
        iii=q.popleft()
        xn,yn=divmod(iii,MM)
        # (xn,yn)=q.popleft()
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,-kk)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx*MM+yy]!=INF:continue
                dist[xx*MM+yy]=dist[xn*MM+yn]+1
                q.append((xx*MM+yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,+kk)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx*MM+yy]!=INF:continue
                dist[xx*MM+yy]=dist[xn*MM+yn]+1
                q.append((xx*MM+yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx*MM+yy]!=INF:continue
                dist[xx*MM+yy]=dist[xn*MM+yn]+1
                q.append((xx*MM+yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(-kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx*MM+yy]!=INF:continue
                dist[xx*MM+yy]=dist[xn*MM+yn]+1
                q.append((xx*MM+yy))
        
        
        
        
    # pprint(maze)
    # for j in dist:print(*j)
    ans=dist[x2*MM+y2]
    if ans==INF:
        ans=-1
    print(ans)  
    
main()

Submission status: Runtime Error

Solution code:
from collections import deque
import math
h,w,k=map(int,input().split())
r=[1, 0, 0, -1] 
c=[0, -1, 1, 0] 
x1,y1,x2,y2=map(int,input().split())
vis=[[False for i in range(w)] for j in range(h)]
arr=[]
for i in range(h):
    ff=list(input())
    arr.append(ff)
f=0
q=deque()
q.append([x1-1,y1-1,0])
vis[x1-1][y1-1]=True
while(len(q)>0):
    curr=q.popleft()
    if curr[0]==x2-1 and curr[1]==y2-1:
        f=curr[2]+2
        break
    for i in range(4):
        row=curr[0]+r[i]
        col=curr[1]+c[i]
        print(curr)
        if row<=h-1 and row>=0 and col>=0 and col<=w-1 and arr[row][col]=='.' and not vis[row][col]:
                vis[row][col]=True
                b=[row,col,curr[2]+1]
                q.append(b)
if f==0:
    print(-1)
    continue
if f%2==1:
  print(math.ceil(f/k))
else:print((f//k)-1)