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: Time Limit Exceeded

Solution code:
# F - Pond Skater
from collections import deque
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:
    x,y = que.popleft()
    i = x-1
    while judge>0 and i>=max(1,x-K) and c[i][y]=='.':
        if d[i][y]<0:
            d[i][y] = d[x][y]+1
            if (i,y)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([i,y])
        i -= 1
    i = x+1
    while judge>0 and i<=min(H,x+K) and c[i][y]=='.':
        if d[i][y]<0:
            d[i][y] = d[x][y]+1
            if (i,y)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([i,y])
        i += 1
    j = y-1
    while judge>0 and j>=max(1,y-K) and c[x][j]=='.':
        if d[x][j]<0:
            d[x][j] = d[x][y]+1
            if (x,j)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([x,j])
        j -= 1
    j = y+1
    while judge>0 and j<=min(W,y+K) and c[x][j]=='.':
        if d[x][j]<0:
            d[x][j] = d[x][y]+1
            if (x,j)==(x2,y2):
                ans = d[x2][y2]
                judge = 0
            que.append([x,j])
        j += 1
print(ans)

Submission status: Time Limit Exceeded

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


def main():
    H, W, K = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    S = [[False]*W for _ in range(H)]
    for i in range(H):
        s = input()
        for j in range(W):
            if s[j] == ".":
                S[i][j] = True

    cost = [[-1]*W for _ in range(H)]

    # 深さ優先探索
    def bfs(x, y, gx, gy):
        stack = deque([[x, y]])
        cost[x][y] = 0
        while stack:
            x, y = stack[0]
            if x == gx and y == gy:
                return
            point = cost[x][y] + 1
            # up
            for i in range(1, K+1):
                if x-i >= 0:
                    if S[x-i][y] and cost[x-i][y] == -1:
                        cost[x-i][y] = point
                        stack.append([x-i, y])
                    elif not S[x-i][y]:
                        break
                else:
                    break
            # down
            for i in range(1, K+1):
                if x+i < H:
                    if S[x+i][y] and cost[x+i][y] == -1:
                        cost[x+i][y] = point
                        stack.append([x+i, y])
                    elif not S[x+i][y]:
                        break
                else:
                    break
            # left
            for i in range(1, K+1):
                if y-i >= 0:
                    if S[x][y-i] and cost[x][y-i] == -1:
                        cost[x][y-i] = point
                        stack.append([x, y-i])
                    elif not S[x][y-i]:
                        break
                else:
                    break
            # right
            for i in range(1, K+1):
                if y+i < W:
                    if S[x][y+i] and cost[x][y+i] == -1:
                        cost[x][y+i] = point
                        stack.append([x, y+i])
                    elif not S[x][y+i]:
                        break
                else:
                    break

            stack.popleft()        

    bfs(sx-1, sy-1, gx-1, gy-1)
    print(cost[gx-1][gy-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

q = deque()
q.append((y2-1, x2-1, 0))
is_visit[x2-1][y2-1] = 0
while len(q) != 0:
    x, y, c = q.popleft()
    # print(is_visit)
    for i in range(1, k+1):
        if x-i >= 0 and map[y][x-i] == '.':
            if is_visit[y][x-i] > c+1:
                is_visit[y][x-i] = c+1
                q.append((x-i, y, c+1))
        else:
            break
    for i in range(1, k+1):
        if x+i < w and map[y][x+i] == '.':
            if is_visit[y][x+i] > c+1:
                is_visit[y][x+i] = c+1
                q.append((x+i, y, c+1))
        else:
            break
    for i in range(1, k+1):
        if y-i >= 0 and map[y-i][x] == '.':
            if is_visit[y-i][x] > c+1:
                is_visit[y-i][x] = c+1
                q.append((x, y-i, c+1))
        else:
            break
    for i in range(1, k+1):
        if y+i < h and map[y+i][x] == '.':
            if is_visit[y+i][x] > c+1:
                is_visit[y+i][x] = c+1
                q.append((x, y+i, c+1))
        else:
            break

ans = is_visit[x1-1][y1-1]
if ans == 10**6:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W,K = map(int,input().split())

x1,y1,x2,y2 = map(int,input().split())
x1-=1
y1-=1
x2-=1
y2-=1

c = []

for i in range(H):

    C = list(input())
    c.append(C)

u = [[(float("inf") , float("inf"))] * W for i in range(H)]
d = [[(float("inf") , float("inf"))] * W for i in range(H)]
l = [[(float("inf") , float("inf"))] * W for i in range(H)]
r = [[(float("inf") , float("inf"))] * W for i in range(H)]

q = deque([("l",0,0,x1,y1) , ("r",0,0,x1,y1) ,("u",0,0,x1,y1) ,("d",0,0,x1,y1)])
u[x1][y1] = (0,0)
d[x1][y1] = (0,0)
l[x1][y1] = (0,0)
r[x1][y1] = (0,0)

while len(q) > 0:

    tmp = q.popleft()
    di,kai,sus,x,y = tmp

    if di == "l" and x != 0 and sus < K and c[x-1][y]!="@" :
        if l[x-1][y] > (kai,sus+1):
            l[x-1][y] = (kai,sus+1)
            q.append( ("l",kai,sus+1,x-1,y) )

    if di == "r" and x != H-1 and sus < K and c[x+1][y]!="@":
        if r[x+1][y] > (kai,sus+1):
            r[x+1][y] = (kai,sus+1)
            q.append( ("r",kai,sus+1,x+1,y) )

    if di == "u" and y != 0 and sus < K and c[x][y-1]!="@":
        if u[x][y-1] > (kai,sus+1):
            u[x][y-1] = (kai,sus+1)
            q.append( ("u",kai,sus+1,x,y-1) )

    if di == "d" and y != W-1 and sus < K and c[x][y+1]!="@":
        if d[x][y+1] > (kai,sus+1):
            d[x][y+1] = (kai,sus+1)
            q.append( ("d",kai,sus+1,x,y+1) )


    if x != 0:
        if l[x-1][y] > (kai+1,1) and c[x-1][y]!="@":
            l[x-1][y] = (kai+1,1)
            q.append( ("l",kai+1,1,x-1,y) )

    if x != H-1:
        if r[x+1][y] > (kai+1,1) and c[x+1][y]!="@":
            r[x+1][y] = (kai+1,1)
            q.append( ("r",kai+1,1,x+1,y) )

    if y != 0:
        if u[x][y-1] > (kai+1,1) and c[x][y-1]!="@":
            u[x][y-1] = (kai+1,1)
            q.append( ("u",kai+1,1,x,y-1) )

    if y != W-1:
        if d[x][y+1] > (kai+1,1) and c[x][y+1]!="@":
            d[x][y+1] = (kai+1,1)
            q.append( ("d",kai+1,1,x,y+1) )

ans = min(l[x2][y2],r[x2][y2],u[x2][y2],d[x2][y2])
if ans[0] == float("inf"):
    print (-1)
else:
    print (ans[0]+1)

#print (r)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from functools import lru_cache
h,w,k = map(int,input().split())
sy,sx,gy,gx = map(int,input().split())
sy,sx,gy,gx = sy-1,sx-1,gy-1,gx-1
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = deque()
now.append((sy,sx,-1))
gone[sy][sx] = 1
if map[gy][gx] == "@":
    print(-1)
    exit()
for ans in range(10 ** 6):
    next = deque()
    while now:
        y,x,status = now.popleft()
        gone[y][x] = 1
        if y == gy and x == gx:
            print(ans)
            exit()
        if status != 0 or (y>0 and map[y-1][x] != "@"):
            for i in range(1,k+1):
                if y-i < 0 or map[y-i][x] == "@" or gone[y-i][x] != 0:
                    break
                else:
                    if gone[y-i][x] == 0:
                        next.append((y-i,x,0))
        if status != 1 or (y<h-1 and map[y+1][x] != "@"):
            for i in range(1,k+1):
                if y +i >= h or map[y+i][x] == "@" or gone[y+i][x] != 0:
                    break
                else:
                    if gone[y + i][x] == 0:
                        next.append((y+i,x,1))
        if status != 2 or (x>0 and map[y][x-1] != "@"):
            for i in range(1,k+1):
                if x - i < 0 or map[y][x-i] == "@" or gone[y][x-i] != 0:
                    break
                else:
                    if gone[y][x-i] == 0:
                        next.append((y,x-i,2))
        if status != 3 or (x<w-1 and map[y][x+1] != "@"):
            for i in range(1, k + 1):
                if x+i >= w or map[y][x+i] == "@" or gone[y][x+i] != 0:
                    break
                else:
                    if gone[y][x+i] == 0:
                        next.append((y,x+i,3))
  #     print(next)
    if next == deque():
        print(-1)
        exit()
    now = next
print(-1)

Submission status: Time Limit Exceeded

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())
  calc=lambda x,y:x*1000007+y
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  from collections import deque
  d=deque()
  d.append((sx,sy))
  s=set()
  while d:
    x,y=d.popleft()
    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 b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append((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 b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append((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 b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append((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 b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append((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: Time Limit Exceeded

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

H,W,K = map(int,readline().split())
x1,y1,x2,y2 = map(int,readline().split())
x1,y1,x2,y2 = x1 - 1,y1 - 1,x2 - 1,y2 - 1

grid = [None] * H
for i in range(H):
  grid[i] = readline().rstrip()
  
# 操作としてあり得るのは、
# ・1かきでKマス進む or @の直前まで進む
# ・1かきでKマス未満進んで方向転換する
# 
# ・前回水をかいてから何マス進んでいるか
# ・前回水をかいて、どのむき(U,D,L,R)に進んでいるか
#  (来たところに戻ることはあり得ないので)
# ・今までに何回水をかいたか
# ・今どこにいるか
# 水かき回数でダイクストラ
# たとえ泳ぐ向きが違っても同じ場所を2回通ることはあり得ない。

import numpy as np
# from numba import njit,i8
from collections import defaultdict

import heapq
# 今まで何回水をかいたか,i,j,前回水をかいてから何マス進んでいるか,どのむきに進んでいるか
def solve():
  def get_turn(d):
    if d in ("U","D"): # 縦方向に進んでいた場合の次の進み先
      return ((0,1,"R"),(0,-1,"L"))
    else:
      return ((1,0,"D"),(-1,0,"U"))
  
  def get_straight(d):
    if d == "U":
      return (-1,0,"U")
    if d == "D":
      return (1,0,"D")
    if d == "L":
      return (0,-1,"L")
    if d == "R":
      return (0,1,"R")
  q = []
  heapq.heapify(q)
  # 最初に進む4方向を入れておく
  seen = defaultdict(int)
  for first in "UDLR":
    c = get_straight(first)
    if 0 <= x1 + c[0] < H and 0 <= y1 + c[1] < W:
      if grid[x1 + c[0]][y1 + c[1]] != "@":
        heapq.heappush(q,(1,x1 + c[0],y1 + c[1],1,c[2]))
  seen[(x1,y1)] 
  while q:
    cost,i,j,swim,dire = heapq.heappop(q)
    #print("cost",cost,"i",i,"j",j,"swim",swim,"dire",dire)
    #print(q)
    if (i,j) in seen and seen[(i,j)] <= cost:
      continue
    seen[(i,j)] = cost
    # 曲がる場合
    cases = get_turn(dire)
    for c in cases:
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          heapq.heappush(q,(cost + 1,i + c[0],j + c[1],1,c[2]))
    # 直進する場合
    c = get_straight(dire)
    if swim < K: # まだKマス進んでいない
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          # コストは増えず、swim距離は増える
          heapq.heappush(q,(cost,i + c[0],j + c[1],swim + 1,c[2]))
    elif swim == K: # すでにKマス進んでいる場合
      # 直進する場合
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          # コストは増えて、swim距離は1に
          heapq.heappush(q,(cost + 1,i + c[0],j + c[1],1,c[2]))
  if (x2,y2) in seen:
    return seen[(x2,y2)]
  else:
    return -1
print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    a, b, x, y = map(int, input().split())
    a -= 1
    b -= 1
    x -= 1
    y -= 1
    C = [input().strip("\n") for _ in range(H)]
    D = [[-1 for _ in range(W)] for h in range(H)]
    D[a][b] = 0
    q = []
    heapify(q)
    for h in range(a):
        #up
        if C[a-h-1][b] == "@": break
        else: heappush(q, (h // K + 1, a - h - 1, b, "ud"))
    for h in range(H-a-1):
        #down
        if C[a + h + 1][b] == "@": break
        else: heappush(q, (h // K + 1, a + h + 1, b, "ud"))
    for w in range(b):
        if C[a][b-w-1] == "@": break
        else: heappush(q, (w//K + 1, a, b-w-1, "lr"))
    for w in range(W - b - 1):
        if C[a][b+w+1] == "@": break
        else: heappush(q, (w//K + 1, a, b+w+1, "lr"))

    while q:
        d, h, w, direc = heappop(q)
        if D[h][w] == -1:
            D[h][w] = d
            if direc == "lr": #udのみ
                for dh in range(h):
                    if C[h-dh-1][w] == "@": break
                    elif D[h-dh-1][w] == -1: heappush(q, (dh//K + d + 1, h-dh-1, w, "ud"))
                for dh in range(H-h-1):
                    if C[h+dh+1][w] == "@": break
                    elif D[h+dh+1][w] == -1: heappush(q, (dh//K + d + 1, h+dh+1, w, "ud"))
            else:
                for dw in range(w):
                    if C[h][w-dw-1] == "@": break
                    elif D[h][w-dw-1] == -1: heappush(q, (dw//K + d + 1, h, w-dw-1, "lr"))
                for dw in range(W-w-1):
                    if C[h][w+dw+1] == "@": break
                    elif D[h][w+dw+1] == -1: heappush(q, (dw//K + d + 1, h, w+dw+1, "lr"))

    print(D[x][y])
    #print(D)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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
                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: Time Limit Exceeded

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


def main():
    H, W, K = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    S = [[False]*W for _ in range(H)]
    for i in range(H):
        s = input()
        for j in range(W):
            if s[j] == ".":
                S[i][j] = True

    cost = [[-1]*W for _ in range(H)]

    # 深さ優先探索
    def bfs(x, y):
        stack = deque([[x, y]])
        cost[x][y] = 0
        while stack:
            x, y = stack[0]
            point = cost[x][y] + 1
            # up
            for i in range(1, K+1):
                if x-i >= 0:
                    if S[x-i][y] and cost[x-i][y] == -1:
                        cost[x-i][y] = point
                        stack.append([x-i, y])
                    elif not S[x-i][y]:
                        break
                else:
                    break
            # down
            for i in range(1, K+1):
                if x+i < H:
                    if S[x+i][y] and cost[x+i][y] == -1:
                        cost[x+i][y] = point
                        stack.append([x+i, y])
                    elif not S[x+i][y]:
                        break
                else:
                    break
            # left
            for i in range(1, K+1):
                if y-i >= 0:
                    if S[x][y-i] and cost[x][y-i] == -1:
                        cost[x][y-i] = point
                        stack.append([x, y-i])
                    elif not S[x][y-i]:
                        break
                else:
                    break
            # right
            for i in range(1, K+1):
                if y+i < W:
                    if S[x][y+i] and cost[x][y+i] == -1:
                        cost[x][y+i] = point
                        stack.append([x, y+i])
                    elif not S[x][y+i]:
                        break
                else:
                    break

            stack.popleft()        

    bfs(sx-1, sy-1)
    print(cost[gx-1][gy-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [INF for _ in range((W+2) * (H+2))]
dist[sh*(W+2)+sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "." and dist[ii*(W+2)+jj] > dist[i*(W+2)+j]:
				dist[ii*(W+2)+jj] = dist[i*(W+2)+j] + 1
				if ii == gh and jj == gw:
					print(dist[ii*(W+2)+jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
			else:
				break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W, K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = list(list(input())for _ in range(H))
cost = [[H*W+1]*W for _ in range(H)]
cost[x1-1][y1-1] = 0
queue = deque([[x1-1,y1-1]])
while queue:
    x,y = queue.popleft()
    for vecx,vecy in [[0,1],[1,0],[-1,0],[0,-1]]:
        for k in range(1,K+1):
            nx,ny = x+k*vecx, y+k*vecy
            if not(0<=nx<H) or not(0<=ny<W):
                break
            if c[nx][ny] == '@':
                break
            if cost[nx][ny] > cost[x][y]+1:
                cost[nx][ny] = cost[x][y]+1
                queue.append([nx,ny])
if cost[x2-1][y2-1] == H*W+1:
    print(-1)
else:
    print(cost[x2-1][y2-1])

Submission status: Time Limit Exceeded

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())
  calc=lambda x,y:x*1000007+y
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  from collections import deque
  d=deque()
  d.append(calc(sx,sy))
  s=set()
  while d:
    x,y=divmod(d.popleft(),1000007)
    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 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 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 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 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: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@':
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    print(d[gx][gy])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

INF=10000000010

H,W,K=[int(i) for i in input().split(" ")]
x1,y1,x2,y2=[int(i)-1 for i in input().split(" ")]
pond=[]
dist=[]
for i in range(H):
    l=[j=="." for j in input()]
    ld=[INF for j in range(W)]
    pond.append(l)
    dist.append(ld)

dist[x1][y1]=0
next=[(x1,y1)]

while len(next)>0:
    _next=[]
    for start in next:
        score=dist[start[0]][start[1]]
        for d in range(1,K+1):
            if start[0]+d>=H or pond[start[0]+d][start[1]]==False:
                break
            if dist[start[0]+d][start[1]]>score+1:
                dist[start[0]+d][start[1]]=score+1
                _next.append((start[0]+d,start[1]))
        for d in range(1,K+1):
            if start[0]-d<0 or pond[start[0]-d][start[1]]==False:
                break
            if dist[start[0]-d][start[1]]>score+1:
                dist[start[0]-d][start[1]]=score+1
                _next.append((start[0]-d,start[1]))

        for d in range(1,K+1):
            if start[1]-d<0 or pond[start[0]][start[1]-d]==False:
                break
            if dist[start[0]][start[1]-d]>score+1:
                dist[start[0]][start[1]-d]=score+1
                _next.append((start[0],start[1]-d))
        for d in range(1,K+1):
            if start[1]+d>=W or  pond[start[0]][start[1]+d]==False:
                break
            if dist[start[0]][start[1]+d]>score+1:
                dist[start[0]][start[1]+d]=score+1
                _next.append((start[0],start[1]+d))
    next=_next


if dist[x2][y2]==INF:
    print(-1)
else:
    print(dist[x2][y2])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W,K = IL()
y1,x1,y2,x2 = IL()
data = SLs(H)
d = [[INF for i in range(W)] for j in range(H)]
flag = [[[0,0,0,0] for i in range(W)] for j in range(H)]

d[y1-1][x1-1] = 0
q = deque([(y1-1,x1-1)])
while q:
  y,x = q.popleft()
  y0,x0 = y+0,x+0
  d0 = d[y0][x0]
  #上
  count = K
  while count:
    count -= 1
    y -= 1
    if 0<=x<W and 0<=y<H:
      if d[y][x] == INF and data[y][x] == "." and flag[y][x][0] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x][0] = count
      if data[y][x] != ".":
        break
    else:
      break
  #下
  y,x = y0,x0
  count = K
  while count:
    count -= 1
    y += 1
    if 0<=x<W and 0<=y<H:
      if d[y][x] == INF and data[y][x] == "." and flag[y][x][1] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x][1] = count
      if data[y][x] != ".":
        break
    else:
      break
  #右
  y,x = y0,x0
  count = K
  while count:
    count -= 1
    x += 1
    if 0<=x<W and 0<=y<H:
      if d[y][x] == INF and data[y][x] == "." and flag[y][x][2] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x][2] = count
      if data[y][x] != ".":
        break
    else:
      break
  #左
  y,x = y0,x0
  count = K
  while count:
    count -= 1
    x -= 1
    if 0<=x<W and 0<=y<H:
      if d[y][x] == INF and data[y][x] == "." and flag[y][x][3] == 0:
        d[y][x] = d0 + 1
        q.append((y,x))
        flag[y][x][3] = count
      if data[y][x] != ".":
        break
    else:
      break
  if d[y2-1][x2-1]!=INF:
    print(d[y2-1][x2-1])
    exit()
else:
  print(-1)