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 sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]

def make_array(dims, fill):
    if len(dims) == 1:
        return [fill]*dims[0]
    nxt = dims[1:]
    ret = [make_array(nxt,fill) for i in range(dims[0])]
    return ret

inf = float("inf")

DP = make_array((h,w,4), inf)

from collections import deque
que = deque()
for i in range(4):
    que.append((x1,y1,i,0))

dxdy = [(-1,0),(1,0),(0,1),(0,-1)]
while que:
    x,y,prev,cost = que.popleft()
    if DP[x][y][prev] <= cost:
        continue
    DP[x][y][prev] = cost
    for i in range(4):
        if i == prev:
            continue
        nprev = i^1
        ddx, ddy = dxdy[i]
        for j in range(1,k+1):
            nx, ny = x+j*ddx, y+j*ddy
            if not (0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny][nprev] > cost+1):
                break
            que.append((nx,ny,nprev,cost+1))

ans = min(DP[x2][y2])
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]

def make_array(dims, fill):
    if len(dims) == 1:
        return [fill]*dims[0]
    nxt = dims[1:]
    ret = [make_array(nxt,fill) for i in range(dims[0])]
    return ret

inf = float("inf")

DP = make_array((h,w,4), inf)

from collections import deque
que = deque()
for i in range(4):
    que.append((x1,y1,i,0))

dxdy = [(-1,0),(1,0),(0,1),(0,-1)]
while que:
    x,y,prev,cost = que.popleft()
    if DP[x][y][prev] <= cost:
        continue
    DP[x][y][prev] = cost
    for i in range(4):
        if i == prev:
            continue
        nprev = i^1
        ddx, ddy = dxdy[i]
        for j in range(1,k+1):
            nx, ny = x+j*ddx, y+j*ddy
            if not (0<=nx<h and 0<=ny<w and board[nx][ny]):
                break
            if DP[nx][ny][nprev] > cost+1:
                que.append((nx,ny,nprev,cost+1))

ans = min(DP[x2][y2])
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [inf for _ in range(h*w)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1*w+y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.' and d[to_x*w+to_y] > d[cur_x*w+cur_y]:
                    d[to_x*w+to_y] = d[cur_x*w+cur_y] + 1
                    que.append((to_x, to_y))
            else:
                break


print(-1 if d[x2*w+y2] == inf else d[x2*w+y2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.' and d[to_x][to_y] > d[cur_x][cur_y]:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
            else:
                break


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x, to_y = to_x + dx, to_y + dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.' and d[to_x][to_y] > d[cur_x][cur_y]:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
            else:
                break


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

Submission status: Time Limit Exceeded

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

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = list("".join(input().rstrip()+"@" for _ in range(h)))
  ans = 0
  stack = [v1]
  next_vs = set()
  while stack:
    for v in stack:
      if v == v2:
        print(ans)
        exit()
      for dr in (-(w+1), -1, 1, w+1):
        for i in range(1, k+1):
          nv = v+dr*i
          if 0 <= nv < h*(w+1) and C[nv] == ".":
            next_vs.add(nv)
          else:
            break
    for v in stack:
      C[v] = "@"
    stack = list(next_vs)
    next_vs = set()
    ans += 1
  else:
    print(-1)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
v1 = x1*(w+1)+y1
v2 = x2*(w+1)+y2
C = list("".join(input().rstrip()+"@" for _ in range(h)))
ans = 0
stack = [v1]
next_vs = set()
while stack:
  for v in stack:
    if v == v2:
      print(ans)
      exit()
    for dr in (-(w+1), -1, 1, w+1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1) and C[nv] == ".":
          next_vs.add(nv)
        else:
          break
  for v in stack:
    C[v] = "@"
  stack = list(next_vs)
  next_vs = set()
  ans += 1
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}

from collections import deque

def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 15
d = [[[inf] * 4 for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = []
for i in range(4):
    d[x1][y1][i] = 0
    heappush(que, (0, x1, y1, i))
    
while len(que):
    dist, cur_x, cur_y, dir = heappop(que)
    if d[cur_x][cur_y][dir] < dist:
        continue
    if cur_x == x2 and cur_y == y2:
        break
    for i, (dx, dy) in enumerate(move):
        memo = dist
        if i != dir:
            memo = -(-dist // k) * k
            
        to_x, to_y = cur_x + dx, cur_y + dy
        if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
            if d[to_x][to_y][i] > memo + 1:
                d[to_x][to_y][i] = memo + 1
                heappush(que, (memo + 1, to_x, to_y, i))


if all(d[x2][y2][i] == inf for i in range(4)):
    print(-1)
else:
    print(-(-min(d[x2][y2]) // k))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 7
d = [[[inf] * 4 for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def dijkstra():
    que = []
    for i in range(4):
        d[x1][y1][i] = 0
        heappush(que, (0, x1, y1, i))
    
    while len(que):
        dist, cur_x, cur_y, dir = heappop(que)
        if d[cur_x][cur_y][dir] < dist:
            continue
        if cur_x == x2 and cur_y == y2:
            break
        for i, (dx, dy) in enumerate(move):
            memo = dist
            if i != dir:
                memo = -(-dist // k) * k
            
            to_x, to_y = cur_x + dx, cur_y + dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y][i] > memo + 1:
                    d[to_x][to_y][i] = memo + 1
                    heappush(que, (memo + 1, to_x, to_y, i))

dijkstra()
if all(d[x2][y2][i] == inf for i in range(4)):
    print(-1)
else:
    print(-(-min(d[x2][y2]) // k))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 7
d = [[[inf] * 4 for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def dijkstra():
    que = []
    for i in range(4):
        d[x1][y1][i] = 0
        heappush(que, (0, x1, y1, i))
    
    while len(que):
        dist, cur_x, cur_y, dir = heappop(que)
    
        for i, (dx, dy) in enumerate(move):
            memo = dist
            if i != dir:
                memo = -(-dist // k) * k
            
            to_x, to_y = cur_x + dx, cur_y + dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y][i] > memo + 1:
                    d[to_x][to_y][i] = memo + 1
                    heappush(que, (memo + 1, to_x, to_y, i))

dijkstra()
if all(d[x2][y2][i] == inf for i in range(4)):
    print(-1)
else:
    print(-(-min(d[x2][y2]) // k))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))
cc = c[:]
  
q = [(0,x1-1,y1-1,0,())]
while(q):
  qq = []
  for a,x,y,kk,d in q:
    #print(x,y,c[x][y])
    if cc[x][y] == '.':
      cc[x][y] = (a,kk)
    else:
      if a < cc[x][y][0] or (a == cc[x][y][0] and kk >= cc[x][y][1]):
        cc[x][y] = (a,kk)
      else:
        continue
    # c[x][y] = min(c[x][y],a)
    # c[x][y] = a
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      if 0 <= x+dx < h and 0 <= y+dy < w and c[x+dx][y+dy] != '@':
        if kk == 0 or d != (dx,dy):
          nk = k-1
          na = a+1
        else:
          nk = kk-1
          na = a
        if cc[x+dx][y+dy] == '.' or na < cc[x+dx][y+dy][0] or (na == cc[x+dx][y+dy][0] and kk >= cc[x+dx][y+dy][1]):
          qq.append((na,x+dx,y+dy,nk,(dx,dy)))
  #print(qq)
  q = qq[:]

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

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

queue = deque([(y1-1, x1-1, 0)])
def bfs(queue):
    while queue:
        y, x, cnt = queue.popleft()
        if y==y2-1 and x==x2-1:
            return cnt
        if checked[y][x]>=1:
            continue
        checked[y][x]=cnt
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if checked[ny][nx]<0:
                    queue.append((ny, nx, cnt+1))
                elif checked[ny][nx]<=checked[y][x]:
                    break
    return -1

print(bfs(queue))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

checked = [[0]*W for _ in range(H)]

queue = deque([(y1-1, x1-1, 0)])
def bfs(queue):
    dist = [[inf]*W for _ in range(H)]
    while queue:
        y, x, cnt = queue.popleft()
        if y==y2-1 and x==x2-1:
            return cnt
        if checked[y][x]==1:
            continue
        checked[y][x]=1
        dist[y][x] = cnt
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if dist[ny][nx]<=dist[y][x]:
                    break
                if not checked[ny][nx]:
                    queue.append((ny, nx, cnt+1))
    return -1

print(bfs(queue))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from heapq import heappop, heappush
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main(C, H, W, S, T, K):
    INF = 10**18
    N = H * W
    q = [5 * S]
    dist = np.full((5 * N), INF, np.int64)
    dist[5 * S] = 0
    move = [0, 1, -1, W, -W]
    B = 5 * N + 10
    while q:
        x = heappop(q)
        dist_x, x = divmod(x, B)
        if dist_x > dist[x]:
            continue
        v, d = divmod(x, 5)
        if d == 0:
            # どちらかに進む
            for i in range(1, 5):
                w = v + move[i]
                y = 5 * w + i
                dist_y = dist_x + 1
                if C[w] and dist_y < dist[y]:
                    dist[y] = dist_y
                    heappush(q, B * dist_y + y)
        else:
            # 直進する
            if dist_x % K != 0:
                w = v + move[d]
                y = 5 * w + d
                dist_y = dist_x + 1
                if C[w] and dist_y < dist[y]:
                    dist[y] = dist_y
                    heappush(q, B * dist_y + y)
            # 止まって向きを変える権利を得る
            y = 5 * v
            dist_y = dist_x + (-dist_x) % K
            if dist_y < dist[y]:
                dist[y] = dist_y
                heappush(q, B * dist_y + y)
    x = dist[5 * T]
    if x == INF:
        return -1
    return dist[5 * T] // K


 
H, W, K = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
 
C = np.zeros((H + 2, W + 2), np.bool_)
"""
tmp1 = np.frombuffer(read(),"S1")
print(tmp1)
tmp1 = tmp1.reshape(H,-1)
print(tmp1)
print(tmp1[:,:W])
"""

C[1:-1, 1:-1] = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'.'
C = C.ravel()
H += 2
W += 2
 
S = W * x1 + y1
T = W * x2 + y2
 
print(main(C, H, W, S, T, K))

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

H,W,K = map(int,input().split())
H = H+2
W = W+2
sx,sy,gx,gy = map(int,input().split())
sx,sy = sy,sx
gx,gy = gy,gx
inf = 10**7

M = [["@"]*W for _ in range(H)]

for h in range(1,H-1):
    M[h][1:-1] = list(input())

dist = [[[[inf,inf] for ___ in range(4)] for _ in range(W)] for __ in range(H)]
visited = [[[False for ___ in range(4)] for _ in range(W)] for __ in range(H)]
movable_state = 0
for h in range(H):
    for w in range(W):
        if M[h][w] == ".":
            movable_state += 4



for i in range(4):
    dist[sy][sx][i] = [0,0]

q = [[0,sx,sy,0],[0,sx,sy,1],[0,sx,sy,2],[0,sx,sy,3]]

def can_go(x,y):
    return M[y][x] == "."

def f(x):
    return x[0]*10**7+x[1]


while q != []:
    c,x,y,to = hq.heappop(q)
    swing,step = dist[y][x][to]
    if to == 0:
        if can_go(x-1,y):
            if step <= K-1:
                dist[y][x-1][0] = min([swing,step+1],dist[y][x-1][0],key=f)
                if not visited[y][x-1][0]:
                    hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
            else:
                dist[y][x-1][0] = min([swing+1,1],dist[y][x-1][0],key=f)
                if not visited[y][x-1][0]:
                    hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
        if can_go(x,y-1):
            dist[y-1][x][1] = min([swing+1,1],dist[y-1][x][1],key=f)
            if not visited[y-1][x][1]:
                hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
        if can_go(x+1,y):
            dist[y][x+1][2] = min([swing+1,1],dist[y][x+1][2],key=f)
            if not visited[y][x+1][2]:
                hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
        if can_go(x,y+1):
            dist[y+1][x][3] = min([swing+1,1],dist[y+1][x][3],key=f)
            if not visited[y+1][x][3]:
                hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
    if to == 1:
        if can_go(x,y-1):
            if step <= K-1:
                dist[y-1][x][1] = min([swing,step+1],dist[y-1][x][1],key=f)
                if not visited[y-1][x][1]:
                    hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
            else:
                dist[y-1][x][1] = min([swing+1,1],dist[y-1][x][1],key=f)
                if not visited[y-1][x][1]:
                    hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
        if can_go(x-1,y):
            dist[y][x-1][0] = min([swing+1,1],dist[y][x-1][0],key=f)
            if not visited[y][x-1][0]:
                hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
        if can_go(x+1,y):
            dist[y][x+1][2] = min([swing+1,1],dist[y][x+1][2],key=f)
            if not visited[y][x+1][2]:
                hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
        if can_go(x,y+1):
            dist[y+1][x][3] = min([swing+1,1],dist[y+1][x][3],key=f)
            if not visited[y+1][x][3]:
                hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
    
    if to == 2:
        if can_go(x+1,y):
            if step <= K-1:
                dist[y][x+1][2] = min([swing,step+1],dist[y][x+1][2],key=f)
                if not visited[y][x+1][2]:
                    hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
            if step == K:
                dist[y][x+1][2] = min([swing+1,1],dist[y][x+1][2],key=f)
                if not visited[y][x+1][2]:
                    hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
        
        if can_go(x-1,y):
            dist[y][x-1][0] = min([swing+1,1],dist[y][x-1][0],key=f)
            if not visited[y][x-1][0]:
                hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
        if can_go(x,y-1):
            dist[y-1][x][1] = min([swing+1,1],dist[y-1][x][1],key=f)
            if not visited[y-1][x][1]:
                hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
        if can_go(x,y+1):
            dist[y+1][x][3] = min([swing+1,1],dist[y+1][x][3],key=f)
            if not visited[y+1][x][3]:
                hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
    
    if to == 3:
        if can_go(x,y+1):
            if step <= K-1:
                dist[y+1][x][3] = min([swing,step+1],dist[y+1][x][3],key=f)
                if not visited[y+1][x][3]:
                    hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
            else:
                dist[y+1][x][3] = min([swing+1,1],dist[y+1][x][3],key=f)
                if not visited[y+1][x][3]:
                    hq.heappush(q,[f(dist[y+1][x][3]),x,y+1,3])
        if can_go(x-1,y):
            dist[y][x-1][0] = min([swing+1,1],dist[y][x-1][0],key=f)
            if not visited[y][x-1][0]:
                hq.heappush(q,[f(dist[y][x-1][0]),x-1,y,0])
        if can_go(x,y-1):
            dist[y-1][x][1] = min([swing+1,1],dist[y-1][x][1],key=f)
            if not visited[y-1][x][1]:
                hq.heappush(q,[f(dist[y-1][x][1]),x,y-1,1])
        if can_go(x+1,y):
            dist[y][x+1][2] = min([swing+1,1],dist[y][x+1][2],key=f)
            if not visited[y][x+1][2]:
                hq.heappush(q,[f(dist[y][x+1][2]),x+1,y,2])
    visited[y][x][to] = True

if (visited[gy][gx][0] | visited[gy][gx][1] | visited[gy][gx][2] | visited[gy][gx][3]) == False:
    print(-1)
    exit()
print(min(dist[gy][gx][0][0],dist[gy][gx][1][0],dist[gy][gx][2][0],dist[gy][gx][3][0])+1)

"""
for h in range(H):
    for w in range(W):
        m = inf
        for i in range(4):
            m = min(m,dist[h][w][i][0])
        print(m,end=" ")
    print("\n")
"""

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# リストの両端の要素に対する編集が必要
# 同一方向に進むときは移動回数が増えないためリストのの先頭に挿入
# この仕組みを実装するためdequeを読み込み

H, W, K = map(int, input().split())
# HとWとKの値それぞれを取得

x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
# リストの先頭要素は0番目として数えられる
# 座標のそれぞれの値から1を引いて取得

grid = [input() for _ in range(H)]
# グリッド部分をH行にわたって取得

INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]
# 無限大の浮動小数点を管理

D = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# 進行方向を座標で管理

q = deque()
for d in range(4):
	path[x1][y1][d] = (1, 0)
	# スタート地点を(1, 0)に設定
	q.append((x1, y1, d, 1, 0))
	# (x, y, 進行方向, 移動回数, 進行済マス数)を要素に追加

while q:
	x, y, d, c, k = q.popleft()
	#要素の削除
	
	# nx, ny: 次の座標
	# nd: 次の進行方向
	# nc: 次の移動回数
	# nk: 次の進行済マス数
	
	for nd in range(4):
		if nd == d:
			dx, dy = D[nd]
			nk = 1 if k == K else k + 1
			nc = c + 1 if k == K else c
		else:
			dx, dy = 0, 0
			nk = 0
			nc = c + 1
		nx = x + dx; ny = y + dy
		if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (nc, nk):
			path[nx][ny][nd] = (nc), (nk)
			if nc == c:
				q.appendleft((nx, ny, nd, nc, nk))
			else:
				q.append((nx, ny, nd, nc, nk))
				
# コストの算出
ans = INF
for d in range(4):
	ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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
from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[INF]*W for _ in range(H)]
dists[r1][c1] = 0
q = deque([(r1,c1)])
while q:
    y,x = q.popleft()
    for dx,dy in 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 dists[ny][nx] <= dists[y][x] + 1: continue
        dists[ny][nx] = dists[y][x] + 1
        q.append((ny,nx))

costs = [INF] * (H*W*4)
costs[(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 dists[ny][nx] >= dists[y][x] + 20: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if costs[(y*W+x)*4+di] <= nc: continue
            costs[(y*W+x)*4+di] = nc
            heapq.heappush(hq, ((nc*H+y)*W+x)*4+di)
        else:
            if costs[(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:
import sys
input = sys.stdin.readline
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
from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[INF]*W for _ in range(H)]
dists[r1][c1] = 0
q = deque([(r1,c1)])
while q:
    y,x = q.popleft()
    for dx,dy in 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 dists[ny][nx] <= dists[y][x] + 1: continue
        dists[ny][nx] = dists[y][x] + 1
        q.append((ny,nx))

costs = [INF] * (H*W*4)
costs[(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 dists[ny][nx] >= dists[y][x] + 100: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if costs[(y*W+x)*4+di] <= nc: continue
            costs[(y*W+x)*4+di] = nc
            heapq.heappush(hq, ((nc*H+y)*W+x)*4+di)
        else:
            if costs[(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:
import sys
input = sys.stdin.readline
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)