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:
from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break
        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
            q.append((i, y))
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break
        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
            q.append((i, y))
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break
        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
            q.append((x, j))
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break
        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
            q.append((x, j))
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-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())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, x+k+1):
        if 0 <= i <= h-1:
            if g[i][y] == "@":
                break
            if dp[i][y] >= c + 1:
                dp[i][y] = c + 1
                q.append((i, y))
            else:
                break
        else:
            break

    for i in range(x-1, x-k-1, -1):
        if 0 <= i <= h-1:
            if g[i][y] == "@":
                break
            if dp[i][y] >= c + 1:
                dp[i][y] = c + 1
                q.append((i, y))
            else:
                break
        else:
            break

    for j in range(y+1, y+k+1):
        if 0 <= j <= w-1:
            if g[x][j] == "@":
                break
            if dp[x][j] >= c + 1:
                dp[x][j] = c + 1
                q.append((x, j))
            else:
                break
        else:
            break

    for j in range(y-1, y-k-1, -1):
        if 0 <= j <= w-1:
            if g[x][j] == "@":
                break
            if dp[x][j] >= c + 1:
                dp[x][j] = c + 1
                q.append((x, j))
            else:
                break
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-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())

g = []
for i in range(h):
    g.append(input())

inf = 10**18
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    for i in range(x+1, x+k+1):
        if 0 <= i <= h-1:
            if g[i][y] == "@":
                break
            if dp[i][y] >= dp[x][y] + 1:
                dp[i][y] = dp[x][y] + 1
                q.append((i, y))
            else:
                break
        else:
            break

    for i in range(x-1, x-k-1, -1):
        if 0 <= i <= h-1:
            if g[i][y] == "@":
                break
            if dp[i][y] >= dp[x][y] + 1:
                dp[i][y] = dp[x][y] + 1
                q.append((i, y))
            else:
                break
        else:
            break

    for j in range(y+1, y+k+1):
        if 0 <= j <= w-1:
            if g[x][j] == "@":
                break
            if dp[x][j] >= dp[x][y] + 1:
                dp[x][j] = dp[x][y] + 1
                q.append((x, j))
            else:
                break
        else:
            break

    for j in range(y-1, y-k-1, -1):
        if 0 <= j <= w-1:
            if g[x][j] == "@":
                break
            if dp[x][j] >= dp[x][y] + 1:
                dp[x][j] = dp[x][y] + 1
                q.append((x, j))
            else:
                break
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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 = [(y,x)]
    d = [[0]*w for i in range(h)]
    while q:
      i,j = q.pop()
      for dy,dx in dd:
          ny,nx = i+dy,j+dx
          if 0 <= ny < h and 0 <= nx < w:
              if c[ny][nx] != "@" and not d[ny][nx]:
                  d[ny][nx] = 1
                  q.append((ny,nx))
    if not d[s][t]:
        print(-1)
        return
    cost = 1/k
    d = defaultdict(lambda : float("inf"))
    for i in range(4):
        d[(y,x,i)] = 0
        q.append((0,y,x,i))

    while q:
        dyx,y,x,p = heappop(q)
        if (y,x) == (s,t):
            print(math.ceil(round(dyx,6)))
            return
        if d[(y,x,p)] < dyx:
            continue

        for i,(dy,dx) in enumerate(dd):
            if i == p:
                nd = dyx + cost
            else:
                nd = math.ceil(round(dyx,6)) + cost
            ny,nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if c[ny][nx] != "@":
                    if nd < d[(ny,nx,i)]:
                        d[(ny,nx,i)] = nd
                        heappush(q,(nd,ny,nx,i))
    return

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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)]
    cost = 1/k
    d = defaultdict(lambda : float("inf"))
    q = []
    for i in range(4):
        d[(y,x,i)] = 0
        q.append((0,y,x,i))

    while q:
        dyx,y,x,p = heappop(q)
        if (y,x) == (s,t):
            print(math.ceil(round(dyx,6)))
            return
        if d[(y,x,p)] < dyx:
            continue

        for i,(dy,dx) in enumerate(dd):
            if i == p:
                nd = dyx + cost
            else:
                nd = math.ceil(round(dyx,6)) + cost
            ny,nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if c[ny][nx] != "@":
                    if nd < d[(ny,nx,i)]:
                        d[(ny,nx,i)] = nd
                        heappush(q,(nd,ny,nx,i))
    print(-1)
    return

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

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            nx.append([x,y+i])
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            nx.append([x,y-i])
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            nx.append([x+i,y])
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            nx.append([x-i,y])
            i+=1

    return 0

C[x1-1][y1-1]=str(0)
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=[]
    if len(taisho)==0 or result>10**6:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

print(result)

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            nx.append([x,y+i])
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            nx.append([x,y-i])
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            nx.append([x+i,y])
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            nx.append([x-i,y])
            i+=1

    return 0

C[x1-1][y1-1]=str(0)
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=[]
    if len(taisho)==0:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

print(result)

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,cn,k):
    nx=[]

    i=1
    while y+i<=W-1 and i<=k:
        A=C[x][y+i]
        if A=='.' or A==str(cn+1):
            C[x][y+i]=str(cn+1)
            nx.append([x,y+i])
            i+=1
        else:
            break
    
    i=1
    while y-i>=0 and i<=k:
        A=C[x][y-i]
        if A=='.' or A==str(cn+1):
            C[x][y-i]=str(cn+1)
            nx.append([x,y-i])
            i+=1
        else:
            break
    
    i=1
    while x+i<=H-1 and i<=k:
        A=C[x+i][y]
        if A=='.' or A==str(cn+1):
            C[x+i][y]=str(cn+1)
            nx.append([x+i,y])
            i+=1
        else:
            break
    
    i=1
    while x-i>=0 and i<=k:
        A=C[x-i][y]
        if A=='.' or A==str(cn+1):
            C[x-i][y]=str(cn+1)
            nx.append([x-i,y])
            i+=1
        else:
            break

    return nx

C[x1-1][y1-1]=str(0)
taisho=keiro(x1-1,y1-1,0,K)
result=1

while C[x2-1][y2-1]=='.':
    next_taisho=[]
    if len(taisho)==0:
        result=-1
        break
    for l in taisho:
        m=keiro(l[0],l[1],result,K)

        for n in m:
            next_taisho.append(n)
    result+=1
    taisho=next_taisho.copy()

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 > reach[nx][ny]: #すでに余裕をもって到達済み
        break
      reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
      Q.append((nx,ny))
      if nx == gx and ny == gy:
        #print(reach)
        print(reach[nx][ny])
        exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if 0<=nx<H and 0<=ny<W:
        if Pond[nx][ny] == "@": #一回蓮があったらその向きはもう無理
          break
        if reach[x][y]+1 < reach[nx][ny]:
          reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
          Q.append((nx,ny))
        if nx == gx and ny == gy:
          #print(reach)
          print(reach[nx][ny])
          exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,cn,k):
    nx=[]

    i=1
    while True:
        if y+i>W-1 or i>k:
            break
        elif C[x][y+i]=='.' or C[x][y+i]==str(cn+1):
            C[x][y+i]=str(cn+1)
            nx.append([x,y+i])
            i+=1
        else:
            break
    
    i=1
    while True:
        if y-i<0 or i>k:
            break
        elif C[x][y-i]=='.' or C[x][y-i]==str(cn+1):
            C[x][y-i]=str(cn+1)
            nx.append([x,y-i])
            i+=1
        else:
            break
    
    i=1
    while True:
        if x+i>H-1 or i>k:
            break
        elif C[x+i][y]=='.' or C[x+i][y]==str(cn+1):
            C[x+i][y]=str(cn+1)
            nx.append([x+i,y])
            i+=1
        else:
            break
    
    i=1
    while True:
        if x-i<0 or i>k:
            break
        elif C[x-i][y]=='.' or C[x-i][y]==str(cn+1):
            C[x-i][y]=str(cn+1)
            nx.append([x-i,y])
            i+=1
        else:
            break

    return nx

C[x1-1][y1-1]=str(0)
taisho=keiro(x1-1,y1-1,0,K)
result=1

while C[x2-1][y2-1]=='.':
    next_taisho=[]
    if len(taisho)==0:
        result=-1
        break
    for l in taisho:
        m=keiro(l[0],l[1],result,K)

        for n in m:
            next_taisho.append(n)
    result+=1
    taisho=next_taisho.copy()

print(result)

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,cn,k):
    nx=[]

    i=1
    while True:
        if y+i>W-1 or C[x][y+i]=='@' or i>k:
            break
        elif C[x][y+i]=='.' or int(C[x][y+i])==cn+1:
            C[x][y+i]=str(cn+1)
            nx.append([x,y+i])
            i+=1
        else:
            break
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]=='@' or i>k:
            break
        elif C[x][y-i]=='.' or int(C[x][y-i])==cn+1:
            C[x][y-i]=str(cn+1)
            nx.append([x,y-i])
            i+=1
        else:
            break
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]=='@' or i>k:
            break
        elif C[x+i][y]=='.' or int(C[x+i][y])==cn+1:
            C[x+i][y]=str(cn+1)
            nx.append([x+i,y])
            i+=1
        else:
            break
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]=='@' or i>k:
            break
        elif C[x-i][y]=='.' or int(C[x-i][y])==cn+1:
            C[x-i][y]=str(cn+1)
            nx.append([x-i,y])
            i+=1
        else:
            break

    return nx

C[x1-1][y1-1]=str(0)
taisho=keiro(x1-1,y1-1,0,K)
result=1

while C[x2-1][y2-1]=='.':
    next_taisho=[]
    if len(taisho)==0:
        result=-1
        break
    for l in taisho:
        m=keiro(l[0],l[1],result,K)

        for n in m:
            next_taisho.append(n)
    result+=1
    taisho=next_taisho.copy()

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())

pond = []
for _ in range(h):
    pond.append(list(input()))

dD = [[10**13 for _ in range(w)] for _ in range(h)]
dU = [[10**13 for _ in range(w)] for _ in range(h)]
dR = [[10**13 for _ in range(w)] for _ in range(h)]
dL = [[10**13 for _ in range(w)] for _ in range(h)]

dD[x1][y1] = 0
dU[x1][y1] = 0
dR[x1][y1] = 0
dL[x1][y1] = 0

q = deque([((x1, y1), "D", 0), ((x1, y1), "U", 0),
           ((x1, y1), "R", 0), ((x1, y1), "L", 0)])


while q:
    v, direction, p = q.popleft()
    x = v[0]
    y = v[1]
    if 0 <= x + 1 < h and 0 <= y < w and pond[x+1][y] == '.' and direction == "D":
        if dD[x+1][y] > dD[x][y] + (p == 0):
            dD[x+1][y] = dD[x][y] + (p == 0)
            if p == 0:
                q.append(((x+1, y), "D", (p+1) % k))
            else:
                q.appendleft(((x+1, y), "D", (p+1) % k))
    elif 0 <= x+1 < h and 0 <= y < w and pond[x+1][y] == '.':
        if dD[x+1][y] > dR[x][y] + 1:
            dD[x+1][y] = dR[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))
        if dD[x+1][y] > dL[x][y] + 1:
            dD[x+1][y] = dL[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))

    if 0 <= x - 1 < h and 0 <= y < w and pond[x-1][y] == '.' and direction == "U":
        if dU[x-1][y] > dU[x][y]+(p == 0):
            dU[x-1][y] = dU[x][y]+(p == 0)
            if p == 0:
                q.append(((x-1, y), "U", (p+1) % k))
            else:
                q.appendleft(((x-1, y), "U", (p+1) % k))
    elif 0 <= x-1 < h and 0 <= y < w and pond[x-1][y] == '.':
        if dU[x-1][y] > dR[x][y] + 1:
            dU[x-1][y] = dR[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))
        if dU[x-1][y] > dL[x][y] + 1:
            dU[x-1][y] = dL[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))

    if 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and direction == "R":
        if dR[x][y+1] > dR[x][y] + (p == 0):
            dR[x][y+1] = dR[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y+1), "R", (p+1) % k))
            else:
                q.appendleft(((x, y+1), "R", (p+1) % k))
    elif 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.':
        if dR[x][y+1] > dD[x][y] + 1:
            dR[x][y+1] = dD[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))
        if dR[x][y+1] > dU[x][y] + 1:
            dR[x][y+1] = dU[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))

    if 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and direction == "L":
        if dL[x][y-1] > dL[x][y] + (p == 0):
            dL[x][y-1] = dL[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y-1), "L", (p+1) % k))
            else:
                q.appendleft(((x, y-1), "L", (p+1) % k))
    elif 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.':
        if dL[x][y-1] > dD[x][y] + 1:
            dL[x][y-1] = dD[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))
        if dL[x][y-1] > dU[x][y] + 1:
            dL[x][y-1] = dU[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))

ans = min(dD[x2][y2], dU[x2][y2], dR[x2][y2], dL[x2][y2])
print(-1 if ans == 10**13 else ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())

pond = []
for _ in range(h):
    pond.append(list(input()))

if k == 1:
    d = [[10**13 for _ in range(w)] for __ in range(h)]
    d[x1][y1] = 0
    q = deque([(x1, y1)])
    while q:
        x, y = q.popleft()
        if 0 <= x+1 < h and 0 <= y < w and pond[x+1][y] == '.' and d[x+1][y] > d[x][y] + 1:
            d[x+1][y] = d[x][y] + 1
            q.append((x+1, y))
        if 0 <= x-1 < h and 0 <= y < w and pond[x-1][y] == '.' and d[x-1][y] > d[x][y] + 1:
            d[x-1][y] = d[x][y] + 1
            q.append((x-1, y))
        if 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and d[x][y+1] > d[x][y] + 1:
            d[x][y+1] = d[x][y] + 1
            q.append((x, y+1))
        if 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and d[x][y-1] > d[x][y] + 1:
            d[x][y-1] = d[x][y] + 1
            q.append((x, y-1))
    print(-1 if d[x2][y2] == 10**13 else d[x2][y2])
    exit()


dD = [[10**13 for _ in range(w)] for __ in range(h)]
dU = [[10**13 for _ in range(w)] for __ in range(h)]
dR = [[10**13 for _ in range(w)] for __ in range(h)]
dL = [[10**13 for _ in range(w)] for __ in range(h)]

dD[x1][y1] = 0
dU[x1][y1] = 0
dR[x1][y1] = 0
dL[x1][y1] = 0

q = deque([((x1, y1), "D", 0), ((x1, y1), "U", 0),
           ((x1, y1), "R", 0), ((x1, y1), "L", 0)])
while q:
    v, direction, p = q.popleft()
    if v == (x2, y2):
        continue
    x = v[0]
    y = v[1]
    if 0 <= x + 1 < h and 0 <= y < w and pond[x+1][y] == '.' and direction == "D":
        if dD[x+1][y] > dD[x][y] + (p == 0):
            dD[x+1][y] = dD[x][y] + (p == 0)
            if p == 0:
                q.append(((x+1, y), "D", (p+1) % k))
            else:
                q.appendleft(((x+1, y), "D", (p+1) % k))
    elif 0 <= x+1 < h and 0 <= y < w and pond[x+1][y] == '.':
        if dD[x+1][y] > dR[x][y] + 1 and direction == "R":
            dD[x+1][y] = dR[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))
        if dD[x+1][y] > dL[x][y] + 1 and direction == "L":
            dD[x+1][y] = dL[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))

    if 0 <= x - 1 < h and 0 <= y < w and pond[x-1][y] == '.' and direction == "U":
        if dU[x-1][y] > dU[x][y]+(p == 0):
            dU[x-1][y] = dU[x][y]+(p == 0)
            if p == 0:
                q.append(((x-1, y), "U", (p+1) % k))
            else:
                q.appendleft(((x-1, y), "U", (p+1) % k))
    elif 0 <= x-1 < h and 0 <= y < w and pond[x-1][y] == '.':
        if dU[x-1][y] > dR[x][y] + 1 and direction == "R":
            dU[x-1][y] = dR[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))
        if dU[x-1][y] > dL[x][y] + 1 and direction == "L":
            dU[x-1][y] = dL[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))

    if 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and direction == "R":
        if dR[x][y+1] > dR[x][y] + (p == 0):
            dR[x][y+1] = dR[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y+1), "R", (p+1) % k))
            else:
                q.appendleft(((x, y+1), "R", (p+1) % k))
    elif 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.':
        if dR[x][y+1] > dD[x][y] + 1 and direction == "D":
            dR[x][y+1] = dD[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))
        if dR[x][y+1] > dU[x][y] + 1 and direction == "U":
            dR[x][y+1] = dU[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))

    if 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and direction == "L":
        if dL[x][y-1] > dL[x][y] + (p == 0):
            dL[x][y-1] = dL[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y-1), "L", (p+1) % k))
            else:
                q.appendleft(((x, y-1), "L", (p+1) % k))
    elif 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.':
        if dL[x][y-1] > dD[x][y] + 1 and direction == "D":
            dL[x][y-1] = dD[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))
        if dL[x][y-1] > dU[x][y] + 1 and direction == "U":
            dL[x][y-1] = dU[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))

ans = min(dD[x2][y2], dU[x2][y2], dR[x2][y2], dL[x2][y2])
print(-1 if ans == 10**13 else 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())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

q = deque([((0, 0), x1-1, y1-1, i) for i in range(4)])
used = [[[False for l in range(4)] for i in range(w)] for j in range(h)]

for i in range(4):
    dp[x1-1][y1-1][i] = (0, 0)

while q:
    count, x, y, d = q.popleft()
    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

            else:
                nextcount = (count[0]+1, 0)

            if dp[x+dx][y+dy][dd] < nextcount:
                continue
            dp[x+dx][y+dy][dd] = nextcount
            q.append((nextcount, x+dx, y+dy, dd))


ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1
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(lambda x: int(x)-1, input().split())

pond = []
for _ in range(h):
    pond.append(list(input()))

dD = [[10**13 for _ in range(w)] for _ in range(h)]
dU = [[10**13 for _ in range(w)] for _ in range(h)]
dR = [[10**13 for _ in range(w)] for _ in range(h)]
dL = [[10**13 for _ in range(w)] for _ in range(h)]

dD[x1][y1] = 0
dU[x1][y1] = 0
dR[x1][y1] = 0
dL[x1][y1] = 0

q = deque([((x1, y1), "D", 0), ((x1, y1), "U", 0),
           ((x1, y1), "R", 0), ((x1, y1), "L", 0)])
while q:
    v, direction, p = q.popleft()
    if v == (x2, y2):
        continue
    x = v[0]
    y = v[1]
    if 0 <= x + 1 < h and 0 <= y < w and pond[x+1][y] == '.' and direction == "D":
        if dD[x+1][y] > dD[x][y] + (p == 0):
            dD[x+1][y] = dD[x][y] + (p == 0)
            if p == 0:
                q.append(((x+1, y), "D", (p+1) % k))
            else:
                q.appendleft(((x+1, y), "D", (p+1) % k))
    elif 0 <= x+1 < h and 0 <= y < w and pond[x+1][y] == '.':
        if dD[x+1][y] > dR[x][y] + 1 and direction == "R":
            dD[x+1][y] = dR[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))
        if dD[x+1][y] > dL[x][y] + 1 and direction == "L":
            dD[x+1][y] = dL[x][y] + 1
            q.append(((x+1, y), "D", 1 % k))

    if 0 <= x - 1 < h and 0 <= y < w and pond[x-1][y] == '.' and direction == "U":
        if dU[x-1][y] > dU[x][y]+(p == 0):
            dU[x-1][y] = dU[x][y]+(p == 0)
            if p == 0:
                q.append(((x-1, y), "U", (p+1) % k))
            else:
                q.appendleft(((x-1, y), "U", (p+1) % k))
    elif 0 <= x-1 < h and 0 <= y < w and pond[x-1][y] == '.':
        if dU[x-1][y] > dR[x][y] + 1 and direction == "R":
            dU[x-1][y] = dR[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))
        if dU[x-1][y] > dL[x][y] + 1 and direction == "L":
            dU[x-1][y] = dL[x][y] + 1
            q.append(((x-1, y), "U", 1 % k))

    if 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.' and direction == "R":
        if dR[x][y+1] > dR[x][y] + (p == 0):
            dR[x][y+1] = dR[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y+1), "R", (p+1) % k))
            else:
                q.appendleft(((x, y+1), "R", (p+1) % k))
    elif 0 <= x < h and 0 <= y+1 < w and pond[x][y+1] == '.':
        if dR[x][y+1] > dD[x][y] + 1 and direction == "D":
            dR[x][y+1] = dD[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))
        if dR[x][y+1] > dU[x][y] + 1 and direction == "U":
            dR[x][y+1] = dU[x][y] + 1
            q.append(((x, y+1), "R", 1 % k))

    if 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.' and direction == "L":
        if dL[x][y-1] > dL[x][y] + (p == 0):
            dL[x][y-1] = dL[x][y] + (p == 0)
            if p == 0:
                q.append(((x, y-1), "L", (p+1) % k))
            else:
                q.appendleft(((x, y-1), "L", (p+1) % k))
    elif 0 <= x < h and 0 <= y-1 < w and pond[x][y-1] == '.':
        if dL[x][y-1] > dD[x][y] + 1 and direction == "D":
            dL[x][y-1] = dD[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))
        if dL[x][y-1] > dU[x][y] + 1 and direction == "U":
            dL[x][y-1] = dU[x][y] + 1
            q.append(((x, y-1), "L", 1 % k))

ans = min(dD[x2][y2], dU[x2][y2], dR[x2][y2], dL[x2][y2])
print(-1 if ans == 10**13 else ans)