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:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):break
  for i in range(4):
    ki = 1
    while ki <= k:
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      ki += 1
      if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
        if dp[nx][ny] == -1:ki = k+1
        if dp[nx][ny] == 0:
          dp[nx][ny] = dp[p[0]][p[1]] + 1
          if (nx == x2) &( ny == y2):exit( print(dp[x2][y2]-1))
          heapq.heappush(que, (dp[nx][ny], [nx,ny]))
          

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flg = 0
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):break
  for i in range(4):
    for ki in range(1,k+1):
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
        if dp[nx][ny] == -1:break
        while dp[nx][ny] == 0:
          dp[nx][ny] = dp[p[0]][p[1]] + 1
          if (nx == x2) &( ny == y2):exit( print(dp[x2][y2]-1))
          heapq.heappush(que, (dp[nx][ny], [nx,ny]))

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

Submission status: Time Limit Exceeded

Solution code:

import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flg = 0
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):break
  for i in range(4):
    for ki in range(1,k+1):
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
        if dp[nx][ny] == -1:break
        if dp[nx][ny] == 0:
          dp[nx][ny] = dp[p[0]][p[1]] + 1
          if (nx == x2) &( ny == y2):exit( print(dp[x2][y2]-1))
          heapq.heappush(que, (dp[nx][ny], [nx,ny]))

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) & ( p[1] == y2):break
  for i in range(4):
    for ki in range(1,k+1):
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      if (nx<0) | (nx>(h-1))| (ny<0) | (ny>(w-1)):break
      if dp[nx][ny] == -1:break
      if 0 < dp[nx][ny] <= dp[p[0]][p[1]]:break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      if (nx == x2) & ( ny == y2):exit(print(dp[x2][y2]-1))
      heapq.heappush(que, (dp[nx][ny], [nx,ny]))

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

Submission status: Time Limit Exceeded

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

def dijkstra():
    dist = [[[10**18]*4 for _ in range(W)] for _ in range(H)]
    pq = []
    
    for i in range(4):
        dist[sx][sy][i] = 0
        heappush(pq, (0, sx, sy, i))
    
    while pq:
        d, cx, cy, dire = heappop(pq)
        
        if dist[cx][cy][dire]<d:
            continue
        
        for nx, ny, ndire in [(cx-1, cy, 0), (cx+1, cy, 1), (cx, cy-1, 2), (cx, cy+1, 2)]:
            if dire==ndire and 0<=nx<H and 0<=ny<W and c[nx][ny]=='.':
                if dist[nx][ny][dire]>d+1:
                    dist[nx][ny][dire] = d+1
                    heappush(pq, (d+1, nx, ny, dire))
        
        for ndire in range(4):
            if dire!=ndire:
                if dist[cx][cy][ndire]>(d+K-1)//K*K:
                    dist[cx][cy][ndire] = (d+K-1)//K*K
                    heappush(pq, ((d+K-1)//K*K, cx, cy, ndire))
    
    return min(dist[gx][gy])

H, W, K = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [input()[:-1] for _ in range(H)]
ans = dijkstra()

if ans==10**18:
    print(-1)
else:
    print((ans+K-1)//K)

Submission status: Time Limit Exceeded

Solution code:

import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) & ( p[1] == y2):break
  for i in range(4):
    for ki in range(1,k+1):
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      if (p[0] == x2) & ( p[1] == y2):break
      if (nx<0) | (nx>(h-1))| (ny<0) | (ny>(w-1)):break
      if dp[nx][ny] == -1:break
      if 0 < dp[nx][ny] <= dp[p[0]][p[1]]:break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      heapq.heappush(que, (dp[nx][ny], [nx,ny]))

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0) | (dp[nx][ny] == (dp[p[0]][p[1]] + 1)):
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0) | (dp[nx][ny] == dp[p[0]][p[1]] + 1):
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys

input = sys.stdin.readline

heap = []

INF = 1000000000

h, w, k = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
s = (x1, y1)
t = (x2, y2)

c = [[True for j in range(w + 2)]]

for i in range(h):
    c_ = input()
    ci = [True]
    for j in range(w):
        ci.append(c_[j] == '@')
    ci.append(True)
    c.append(ci)

c.append([True for j in range(w + 2)])

heappush(heap, (0, 0, s))

vis = [[[INF for j in range(w + 2)] for i in range(h + 2)] for _ in range(4)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

ans = -1

while len(heap) > 0:
    cost, d, p = heappop(heap)
    if vis[d][p[0]][p[1]] < cost:
        continue
    vis[d][p[0]][p[1]] = -1
    if p == t:
        ans = (cost + k - 1) // k
        break

    next_p = (p[0] + direction[d][0], p[1] + direction[d][1])
    if not c[next_p[0]][next_p[1]] and vis[d][next_p[0]][next_p[1]] > (cost + 1):
        vis[d][next_p[0]][next_p[1]] = cost + 1
        heappush(heap, (cost + 1, d, next_p))

    next_cost = (cost + k - 1) // k * k
    if vis[(d+1) % 4][p[0]][p[1]] > next_cost:
        vis[(d+1) % 4][p[0]][p[1]] = next_cost
        heappush(heap, (next_cost, (d+1) % 4, p))
    # for i in range(4):
    #     if vis[i][p[0]][p[1]] > next_cost:
    #         vis[i][p[0]][p[1]] = next_cost
    #         heappush(heap, (next_cost, i, p))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flg = 0
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0) | (dp[nx][ny] >= (dp[p[0]][p[1]] + 1)):
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys

input = sys.stdin.readline

heap = []

INF = 1000000000

h, w, k = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
s = (x1, y1)
t = (x2, y2)

c = [[True for j in range(w + 2)]]

for i in range(h):
    c_ = input()
    ci = [True]
    for j in range(w):
        ci.append(c_[j] == '@')
    ci.append(True)
    c.append(ci)

c.append([True for j in range(w + 2)])

heappush(heap, (0, 0, s))

vis = [[[INF for j in range(w + 2)] for i in range(h + 2)] for _ in range(4)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

ans = -1

while len(heap) > 0:
    cost, d, p = heappop(heap)
    if vis[d][p[0]][p[1]] < cost:
        continue
    vis[d][p[0]][p[1]] = -1
    if p == t:
        ans = (cost + k - 1) // k
        break

    next_p = (p[0] + direction[d][0], p[1] + direction[d][1])
    if not c[next_p[0]][next_p[1]] and vis[d][next_p[0]][next_p[1]] > (cost + 1):
        vis[d][next_p[0]][next_p[1]] = cost + 1
        heappush(heap, (cost + 1, d, next_p))

    next_cost = (cost + k - 1) // k * k
    for i in range(4):
        if vis[i][p[0]][p[1]] > next_cost:
            vis[i][p[0]][p[1]] = next_cost
            heappush(heap, (next_cost, i, p))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys

input = sys.stdin.readline

heap = []

h, w, k = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
s = (x1, y1)
t = (x2, y2)

c = [[True for j in range(w + 2)]]

for i in range(h):
    c_ = input()
    ci = [True]
    for j in range(w):
        ci.append(c_[j] == '@')
    ci.append(True)
    c.append(ci)

c.append([True for j in range(w + 2)])

heappush(heap, (0, 0, s))

vis = [[[False for j in range(w + 2)] for i in range(h + 2)] for _ in range(4)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

ans = -1

while len(heap) > 0:
    cost, d, p = heappop(heap)
    if vis[d][p[0]][p[1]]:
        continue
    vis[d][p[0]][p[1]] = True
    if p == t:
        ans = (cost + k - 1) // k
        break

    next_p = (p[0] + direction[d][0], p[1] + direction[d][1])
    if not c[next_p[0]][next_p[1]] and not vis[d][next_p[0]][next_p[1]]:
        heappush(heap, (cost + 1, d, next_p))

    for i in range(4):
        if not vis[i][p[0]][p[1]]:
            next_cost = (cost + k - 1) // k * k
            heappush(heap, (next_cost, i, p))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

input = sys.stdin.readline

heap = []

h, w, k = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
s = (x1, y1)
t = (x2, y2)

c = [[True for j in range(w + 2)]]

for i in range(h):
    c_ = input()
    ci = [True]
    for j in range(w):
        ci.append(c_[j] == '@')
    ci.append(True)
    c.append(ci)

c.append([True for j in range(w + 2)])

heapq.heappush(heap, (0, 0, s))

vis = [[[False for j in range(w + 2)] for i in range(h + 2)] for _ in range(4)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

ans = -1

while len(heap) > 0:
    cost, d, p = heapq.heappop(heap)
    if vis[d][p[0]][p[1]]:
        continue
    vis[d][p[0]][p[1]] = True
    if p == t:
        ans = (cost + k - 1) // k
        break

    next_p = (p[0] + direction[d][0], p[1] + direction[d][1])
    if not c[next_p[0]][next_p[1]] and not vis[d][next_p[0]][next_p[1]]:
        heapq.heappush(heap, (cost + 1, d, next_p))

    for i in range(4):
        if not vis[i][p[0]][p[1]]:
            next_cost = (cost + k - 1) // k * k
            heapq.heappush(heap, (next_cost, i, p))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

heap = []

h, w, k = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
s = (x1, y1)
t = (x2, y2)

c = [[True for j in range(w + 2)]]

for i in range(h):
    c_ = input()
    ci = [True]
    for j in range(w):
        ci.append(c_[j] == '@')
    ci.append(True)
    c.append(ci)

c.append([True for j in range(w + 2)])

heapq.heappush(heap, (0, 0, s))

vis = [[[False for j in range(w + 2)] for i in range(h + 2)] for _ in range(4)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

ans = -1

while len(heap) > 0:
    cost, d, p = heapq.heappop(heap)
    if vis[d][p[0]][p[1]]:
        continue
    vis[d][p[0]][p[1]] = True
    if p == t:
        ans = (cost + k - 1) // k
        break

    next_p = (p[0] + direction[d][0], p[1] + direction[d][1])
    if not c[next_p[0]][next_p[1]] and not vis[d][next_p[0]][next_p[1]]:
        heapq.heappush(heap, (cost + 1, d, next_p))

    for i in range(4):
        if not vis[i][p[0]][p[1]]:
            next_cost = (cost + k - 1) // k * k
            heapq.heappush(heap, (next_cost, i, p))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

heap = []

h, w, k = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
s = (x1, y1)
t = (x2, y2)

c = [[True for j in range(w + 2)]]

for i in range(h):
    c_ = input()
    ci = [True]
    for j in range(w):
        ci.append(c_[j] == '@')
    ci.append(True)
    c.append(ci)

c.append([True for j in range(w + 2)])

heapq.heappush(heap, (0, 0, s))

vis = [[[False for j in range(w + 2)] for i in range(h + 2)] for _ in range(4)]

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

ans = -1

while len(heap) > 0:
    cost, d, p = heapq.heappop(heap)
    if vis[d][p[0]][p[1]]:
        continue
    vis[d][p[0]][p[1]] = True
    if p == t:
        ans = (cost + k - 1) // k

    next_p = (p[0] + direction[d][0], p[1] + direction[d][1])
    if not c[next_p[0]][next_p[1]]:
        heapq.heappush(heap, (cost + 1, d, next_p))

    for i in range(4):
        if cost % k == 0:
            next_cost = cost
        else:
            next_cost = (cost // k + 1) * k

        heapq.heappush(heap, (next_cost, i, p))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = deque()
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p = que.popleft()
  #if (p[0] == x2) & (p[1] == y2):
  #  break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0) | (dp[nx][ny] >= (dp[p[0]][p[1]] + 1)):
        que.append((nx,ny))
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = deque()
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p = que.popleft()
  #if (p[0] == x2) & (p[1] == y2):
  #  break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0) | (
            (dp[nx][ny] >= (dp[p[0]][p[1]] + 1)) & (dp[nx][ny] > 0)):
        que.append((nx,ny))
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

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

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = [(0, x1, y1)]
    dist[x1][y1] = 0
    while q:
        d, i, j = heappop(q)
        if dist[i][j] < d: continue
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] <= d + 1: continue
                heappush(q, (d + 1, ni, nj))
                dist[ni][nj] = d + 1
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] <= d + 1: continue
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0

    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K

        ni, nj = i + dr[d][0], j + dr[d][1]
        if 0 <= ni < H and 0 <= nj < W:
            if C[ni][nj] != '@':
                timeninj = time[ni][nj]
                if timeninj[d] > t + 1:
                    q.append((t + 1, ni, nj, d))
                    timeninj[d] = t + 1

        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                if nt == t:
                    q.append((nt, i, j, nd))
                else:
                    q.appendleft((nt, i, j, nd))
                timeij[nd] = nt

    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0

    while q:
        t, i, j, d = q.pop()

        ni, nj = i + dr[d][0], j + dr[d][1]
        if 0 <= ni < H and 0 <= nj < W:
            if C[ni][nj] != '@':
                timeninj = time[ni][nj]
                if timeninj[d] > t + 1:
                    q.append((t + 1, ni, nj, d))
                    timeninj[d] = t + 1

        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                if nt == t:
                    q.append((nt, i, j, nd))
                else:
                    q.appendleft((nt, i, j, nd))
                timeij[nd] = nt

    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                if nt == t:
                    q.append((nt, i, j, nd))
                else:
                    q.appendleft((nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            q.append((t + 1, ni, nj, d))
            timeninj[d] = t + 1
    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                q.appendleft((nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            q.append((t + 1, ni, nj, d))
            timeninj[d] = t + 1
    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[10**12] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = []
    for i in range(4):
        heappush(q, (0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = heappop(q)
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                heappush(q, (nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            heappush(q, (t + 1, ni, nj, d))
            timeninj[d] = t + 1
    ans = min(time[x2][y2][i] for i in range(4))
    if ans == 10**12:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[-1] * W for _ in range(H)]
    q = [(0, x1, y1)]
    while q:
        d, i, j = heappop(q)
        if dist[i][j] >= 0: continue
        dist[i][j] = d
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] >= 0: continue
                heappush(q, (d + 1, ni, nj))
    print(dist[x2][y2])

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)