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:
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [INF] * (H*W*4)
dists[(r1*W+c1)*4] = 0
hq = [(r1*W+c1)*4]
heapq.heapify(hq)
while hq:
    v = heapq.heappop(hq)
    cp,d = divmod(v,4)
    cy,x = divmod(cp,W)
    c,y = divmod(cy,H)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if dists[(y*W+x)*4+di] <= nc: continue
            dists[(y*W+x)*4+di] = nc
            heapq.heappush(hq, ((nc*H+y)*W+x)*4+di)
        else:
            if dists[(ny*W+nx)*4+di] <= c+1: continue
            heapq.heappush(hq, (((c+1)*H+ny)*W+nx)*4+di)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[[INF]*4 for _ in range(W)] for _ in range(H)]
dists[r1][c1][0] = 0
hq = [(r1*W+c1)*4]
heapq.heapify(hq)
while hq:
    v = heapq.heappop(hq)
    cp,d = divmod(v,4)
    cy,x = divmod(cp,W)
    c,y = divmod(cy,H)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if dists[y][x][di] <= nc: continue
            dists[y][x][di] = nc
            heapq.heappush(hq, ((nc*H+y)*W+x)*4+di)
        else:
            if dists[ny][nx][di] <= c+1: continue
            heapq.heappush(hq, (((c+1)*H+ny)*W+nx)*4+di)
print(-1)

Submission status: Time Limit Exceeded

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

def calc():
  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
  board=[input() for _ in range(h)]
  q=collections.deque()
  q.append((sx,sy))
  checked=[[0]*w for _ in range(h)]
  checked[sy][sx]=1
  cost=[[10**18]*w for _ in range(h)]
  cost[sy][sx]=0
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  while len(q)!=0:
    x,y=q.popleft()
    c=cost[y][x]
    for i in range(4):
      for j in range(1,k+1):
        if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
          break
        if board[y+j*dy[i]][x+j*dx[i]]=='@':
          break
        if cost[y+j*dy[i]][x+j*dx[i]]<=c:
          break
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
  if cost[gy][gx]==10**18:
    print(-1)
  else:
    print(cost[gy][gx])
calc()

Submission status: Time Limit Exceeded

Solution code:
import collections

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
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      q.append((x+j*dx[i],y+j*dy[i]))
      cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[[INF]*4 for _ in range(W)] for _ in range(H)]
dists[r1][c1][0] = 0
hq = [(0,(r1*W+c1)*4)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    p,d = divmod(v,4)
    y,x = divmod(p,W)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if dists[y][x][di] <= nc: continue
            dists[y][x][di] = nc
            heapq.heappush(hq, (nc,p*4+di))
        else:
            if dists[ny][nx][di] <= c+1: continue
            heapq.heappush(hq, (c+1,(ny*W+nx)*4+di))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[[INF]*4 for _ in range(W)] for _ in range(H)]
dists[r1][c1][0] = 0
hq = [(0,(r1*W+c1)*4)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    p,d = divmod(v,4)
    y,x = divmod(p,W)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        if di != d:
            nc = c + (K-c)%K
            if dists[y][x][di] <= nc: continue
            dists[y][x][di] = nc
            heapq.heappush(hq, (nc,p*4+di))
        else:
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if C[ny][nx] == '@': continue
            if dists[ny][nx][di] <= c+1: continue
            heapq.heappush(hq, (c+1,(ny*W+nx)*4+di))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


def solve(field, s, t, k):
    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0
    MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]

    q = [(0, s, 0, k)]
    while q:
        cost, v, direction, remaining = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = ((cost - 1) // k + 1) * k + 1
        for di, ax in MOVE:
            if -di == direction:
                continue
            u = v + di
            if field[u] == '@':
                continue
            if di == direction and remaining > 0:
                nc = cost + 1
                nr = remaining - 1
            else:
                nc = ceiling
                nr = k - 1
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, u, di, nr))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = (i-1 for i in map(int,input().split()))
grid = []
inf = 1<<30
reach = [[inf for _ in range(W)] for _ in range(H)]
reach[sx][sy]=0
dif = [(1,0),(-1,0),(0,1),(0,-1)] #向かう方向

for i in range(H):
    grid.append(list(input()))

que = deque([(sx,sy)])
while que:
    x,y = que.popleft()
    for i in range(4): #方向決め
        for k in range(1,K+1):
            nx = x+k*dif[i][0]
            ny = y+k*dif[i][1]
            if nx<0 or nx>=H or ny<0 or ny>= W or grid[nx][ny] == "@":
                break
            if reach[x][y]+1 < reach[nx][ny]:
                reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
                que.append((nx,ny))
            if nx == gx and ny == gy:
                print(reach[nx][ny])
                exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
n=h*w
es=[[] for _ in range(n)]
sx,sy,gx,gy=map(int,input().split())
grid=[]
for i in range(h):
    grid+=[1 if s=='.' else 0 for s in input()]
for i in range(n):
    if grid[i]==1:
        for j in range(1,k+1):
            if i//w==(i+j)//w and grid[i+j]==1:
                es[i].append(i+j)
                es[i+j].append(i)
            else:
                break
        for j in range(1,k+1):
            if i%w==(i+j*w)%w and i+j*w<n and grid[i+j*w]==1:
                es[i].append(i+j*w)
                es[i+j*w].append(i)
            else:
                break

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u in edges[v]:
            if not visited[u]:
                new_dist = dist_v + 1
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

d=dijkstra(es, n, (sx-1)*w+(sy-1))
ans=d[(gx-1)*w+(gy-1)]
print(-1 if ans==float('inf') else ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
SX, SY, GX, GY = lr()
SX -= 1; SY -= 1; GX -= 1; GY -= 1
pond = [sr() for _ in range(H)]
INF = 10 ** 10
dist = [[INF] * W for _ in range(H)]
dist[SX][SY] = 0
que = deque([(0, SX, SY)])
UDLR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
    d, px, py = que.popleft()
    if px == GX and py == GY:
        print(d); exit()
    if dist[px][py] < d:
        continue
    nd = d + 1
    for dx, dy in UDLR:
        nx = px + dx; ny = py + dy
        for _ in range(K):
            if not (0 <= nx < H) or not (0 <= ny < W) \
                    or dist[nx][ny] < nd or pond[nx][ny] == '@':
                break
            que.append((nd, nx, ny))
            dist[nx][ny] = nd
            nx += dx; ny += dy

print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
# from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
# pp=pprint
INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[INF]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                break
                # 更に伸ばす必要はない
            if maze[nx][ny]=="@":
                break
                # 蓮の向こうにはいけないので
            if cost[nx][ny]<=cost[x][y]:
                break
                # 更新を1回以上受けていて、更に良くならない場合はbreak
            # if cost[nx][ny]==INF:
            cost[nx][ny]=cost[x][y]+1
            todo.append((nx,ny))
                # 更新されてなければ、[x][y]から1マス先を更新、キューに突っ込む


# pp(cost)
ans=cost[x2][y2]
if ans==INF:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
# INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                break
                # 更に伸ばす必要はない
            if maze[nx][ny]=="@":
                break
                # 蓮の向こうにはいけない
            # if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
            #     # 更新を1回以上受けていて、更に良くならない場合はbreak
            #     break
            if cost[nx][ny]==-1:
                cost[nx][ny]=cost[x][y]+1
                todo.append((nx,ny))


# pp(cost)
ans=cost[x2][y2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
# INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                continue
            if maze[nx][ny]=="@":
                break
            if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
                continue
            if cost[nx][ny]!=-1:
                continue
            cost[nx][ny]=cost[x][y]+1
            todo.append((nx,ny))


# pp(cost)
ans=cost[x2][y2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
# INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                continue
            if maze[nx][ny]=="@":
                break
            # if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
            #     break
            if cost[nx][ny]!=-1:
                continue
            cost[nx][ny]=cost[x][y]+1
            todo.append((nx,ny))


# pp(cost)
ans=cost[x2][y2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from collections import defaultdict

h, w, k = [int(x) for x in input().split()]
x1, y1, x2, y2 = [int(x) for x in input().split()]
arr = []
for i in range(h):
    arr.append(list(input()))

graph = defaultdict(list)
for i in range(h):
    for j in range(w):
        if arr[i][j] == '@':
            graph[(i, j)] = []
            continue
        for l in range(1, k+1):
            if i-l >= 0:
                if arr[i-l][j] == '@':
                    break
                graph[(i, j)].append((1, i-l, j))
            else:
                break

        for l in range(1, k+1):
            if i+l < h:
                if arr[i+l][j] == '@':
                    break
                graph[(i, j)].append((1, i+l, j))
            else:
                break

        for l in range(1, k+1):
            if j-l >= 0:
                if arr[i][j-l] == '@':
                    break
                graph[(i, j)].append((1, i, j-l))
            else:
                break

        for l in range(1, k+1):
            if j+l < w:
                if arr[i][j+l] == '@':
                    break
                graph[(i, j)].append((1, i, j+l))
            else:
                break

heap = [(0, x1-1, y1-1)]
strokes = 0
flag = True
visited = {}

while heap:
    c, x, y = heappop(heap)
    if x == x2-1 and y == y2-1:
        flag = False
        strokes = c
        break
    visited[(x, y)] = c
    for i in range(len(graph[(x, y)])):
        r, p, q = graph[(x, y)][i]
        if (p, q) not in visited:
            heappush(heap, (c+r, p, q))
        else:
            if visited[(p, q)] > c+r:
                heappush(heap, (c+r, p, q))

if not flag:
    print(strokes)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!python3

from heapq import heappop, heappush

LI = lambda: list(map(int, input().split()))

# input
H, W, K = LI()
x1, y1, x2, y2 = [v - 1 for v in LI()]
C = [input() for _ in range(H)]

INF = 10 ** 10
w = [[[(INF, 0)] * 4 for _ in range(W)] for _ in range(H)]


def forward(d, x, y):
    if d == 0:
        x -= 1
    elif d == 1:
        x += 1
    elif d == 2:
        y -= 1
    else:
        y += 1
    return x, y


def main():
    hq = []
    for i in range(4):
        w[x1][y1][i] = (1, 0)
        hq.append((1, 0, x1, y1, i))
    while hq:
        # cost, k, x, y, direction
        c, k, x, y, d = heappop(hq)
        if w[x][y][d] < (c, k):
            continue
        x_, y_ = forward(d, x ,y)
        if 0 <= x_ < H and 0 <= y_ < W:
            if C[x_][y_] == ".":
                if k < K:
                    if w[x_][y_][d] > (c, k + 1):
                        w[x_][y_][d] = (c, k + 1)
                        heappush(hq, (c, k + 1, x_, y_, d))
                else:
                    if w[x_][y_][d] > (c + 1, 1):
                        w[x_][y_][d] = (c + 1, 1)
                        heappush(hq, (c + 1, 1, x_, y_, d))
                if x_ == x2 and y_ == y2:
                    break
        for i in range(4):
            if i == d:
                continue
            if w[x][y][i] > (c + 1, 0):
                w[x][y][i] = (c + 1, 0)
                t = (c + 1, 0, x, y, i)
                heappush(hq, t)

    ans = min(w[x2][y2])[0]
    ans = -1 if ans == INF else ans
    print(ans)


if __name__ == "__main__":
    main()

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
x2 -= 1
y1 -= 1
y2 -= 1
# C[h][w]
C = [list(input()) for _ in range(h)]

dist = [[10 ** 10] * w for _ in range(h)]

dist[x1][y1] = 0
que = deque([])
que.append((x1, y1))

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

while que:
    a, b = que.popleft()
    d = dist[a][b]
    if a == x2 and b == y2:
        print(dist[x2][y2])
        exit()
    for i in range(4):
        cx = a + dx[i]
        cy = b + dy[i]
        if cx < 0 or cx >= h or cy < 0 or cy >= w:
            continue
        if C[cx][cy] == "@":
            continue
        for j in range(1, k + 1):
            nx = a + dx[i] * j
            ny = b + dy[i] * j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                break
            if C[nx][ny] == "@":
                break
            if dist[nx][ny] == 10 ** 10:
                dist[nx][ny] = d + 1
                que.append((nx, ny))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
#

import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W,K=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    mas=[list(input()) for i in range(H)]
    dist=[[-1]*W for i in range(H)]
    qu=deque([(x1,y1)])
    dist[x1][y1]=0
    qup=qu.popleft
    qua=qu.append
    d=((-1,0),(1,0),(0,-1),(0,1))
    while(len(qu)>0):
        v=qup()
        for di in d:
            for i in range(1,K+1):
                nvh=v[0]+i*di[0]
                nvw=v[1]+i*di[1]
                if nvh<0 or nvh>=H or nvw<0 or nvw>=W or mas[nvh][nvw]=="@":
                    break
                if dist[nvh][nvw]==-1:
                    dist[nvh][nvw]=dist[v[0]][v[1]]+1
                    qua((nvh,nvw))
    print(dist[x2][y2])
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

m = [[-1] * w for _ in range(h)]
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '.':
            m[hh][ww] = h*w

from collections import deque
q = deque()

q.append((0, x1, y1))
while q:
    s, x, y = q.popleft()

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or m[xx][yy] == -1:
            break
        if m[xx][yy] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        m[xx][yy] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or m[xx][yy] == -1:
            break
        if m[xx][yy] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        m[xx][yy] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or m[xx][yy] == -1:
            break
        if m[xx][yy] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        m[xx][yy] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or m[xx][yy] == -1:
            break
        if m[xx][yy] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        m[xx][yy] = s+1
        q.append((s+1, xx, yy))

print(-1)

Submission status: Time Limit Exceeded

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

xxx = set()
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '@':
            xxx.add((hh, ww))

from collections import deque
q = deque()

q.append((0, x1, y1))
d = {}
d[(x1, y1)] = 0
while q:
    s, x, y = q.popleft()

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        q.append((s+1, xx, yy))

print(-1)

Submission status: Time Limit Exceeded

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

xxx = set()
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '@':
            xxx.add((hh, ww))

from heapq import heappush, heappop
q = []
heappush(q, (0, x1, y1))
d = {}
while q:
    s, x, y = heappop(q)

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!python3

from numba import jit
from heapq import heappop, heappush

LI = lambda: list(map(int, input().split()))

# input
H, W, K = LI()
x1, y1, x2, y2 = [v - 1 for v in LI()]
C = [input() for _ in range(H)]

INF = 10 ** 10
n = 4 * H * W
w = [(INF, 0)] * n


def to_id(x, y, d):
    return 4 * (W * x + y) + d


def to_xy(i):
    s = i // 4
    y = s % W
    x = (s - y) // W
    return x, y


def forward(i):
    s = i % 4
    if s == 0:
        return i - (4 * W)
    if s == 1:
        if i // 4 % W == W - 1:
            return INF
        return i + 4
    if s == 2:
        return i + (4 * W)
    if s == 3:
        if i // 4 % W == 0:
            return INF
        return i - 4


@jit(cache=True)
def main():
    hq = []
    for d in range(4):
        i = to_id(x1, y1, d)
        w[i] = (1, 0)
        heappush(hq, (1, 0, i))
    while hq:
        # cost, k, i
        c, k, i = heappop(hq)
        if w[i] < (c, k):
            continue
        j = forward(i)
        if 0 <= j < n:
            x, y = to_xy(j)
            if C[x][y] == ".":
                if k < K:
                    if w[j] > (c, k + 1):
                        w[j] = (c, k + 1)
                        heappush(hq, (c, k + 1, j))
                else:
                    if w[j] > (c + 1, 1):
                        w[j] = (c + 1, 1)
                        heappush(hq, (c + 1, 1, j))
            if x == x2 and y == y2:
                break

        s = i % 4
        v = i - s
        for d in range(4):
            if s == d:
                continue
            j = v + d
            if w[j] > (c + 1, 0):
                w[j] = (c + 1, 0)
                t = (c + 1, 0, j)
                heappush(hq, t)

    i = to_id(x2, y2, 0)
    ans = min(w[i : i + 4])[0]
    ans = -1 if ans == INF else ans
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

from heapq import heappop, heappush

LI = lambda: list(map(int, input().split()))

# input
H, W, K = LI()
x1, y1, x2, y2 = [v - 1 for v in LI()]
C = [input() for _ in range(H)]

INF = 10 ** 10
n = 4 * H * W
w = [(INF, 0)] * n


def to_id(x, y, d):
    return 4 * (W * x + y) + d


def to_xy(i):
    s = i // 4
    y = s % W
    x = (s - y) // W
    return x, y


def forward(i):
    s = i % 4
    if s == 0:
        return i - (4 * W)
    if s == 1:
        if i // 4 % W == W - 1:
            return INF
        return i + 4
    if s == 2:
        return i + (4 * W)
    if s == 3:
        if i // 4 % W == 0:
            return INF
        return i - 4


def main():
    hq = []
    for d in range(4):
        i = to_id(x1, y1, d)
        w[i] = (1, 0)
        heappush(hq, (1, 0, i))
    while hq:
        # cost, k, i
        c, k, i = heappop(hq)
        if w[i] < (c, k):
            continue
        j = forward(i)
        if 0 <= j < n:
            x, y = to_xy(j)
            if C[x][y] == ".":
                if k < K:
                    if w[j] > (c, k + 1):
                        w[j] = (c, k + 1)
                        heappush(hq, (c, k + 1, j))
                else:
                    if w[j] > (c + 1, 1):
                        w[j] = (c + 1, 1)
                        heappush(hq, (c + 1, 1, j))
            if x == x2 and y == y2:
                break

        s = i % 4
        v = i - s
        for d in range(4):
            if s == d:
                continue
            j = v + d
            if w[j] > (c + 1, 0):
                w[j] = (c + 1, 0)
                t = (c + 1, 0, j)
                heappush(hq, t)

    i = to_id(x2, y2, 0)
    ans = min(w[i : i + 4])[0]
    ans = -1 if ans == INF else ans
    print(ans)


if __name__ == "__main__":
    main()