Problem:


Score : 600 points

Problem Statement

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered.
The square (i,j) has a lotus leaf on it if c_{ij} is @, and it does not if c_{ij} is ..

In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west.
The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2).
If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Constraints

1 \leq H,W,K \leq 10^6

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}

Output

Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print -1 if the travel is impossible.

Sample Input 1

3 5 2
3 2 3 4
.....
.@..@
..@..

Sample Output 1

5

Initially, Snuke is at the square (3,2).
He can reach the square (3, 4) by making five strokes as follows:

From (3, 2), go west one square to (3, 1).

From (3, 1), go north two squares to (1, 1).

From (1, 1), go east two squares to (1, 3).

From (1, 3), go east one square to (1, 4).

From (1, 4), go south two squares to (3, 4).

Sample Input 2

1 6 4
1 1 1 6
......

Sample Output 2

2

Sample Input 3

3 3 1
2 1 2 3
.@.
.@.
.@.

Sample Output 3

-1



Sample input:
3 5 2
3 2 3 4
.....
.@..@
..@..


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    if S[x0][y0]=='@':return 0
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if S[x][y]=='@':break
          if d[x][y] < d[x0][y0] + 1: break
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    if S[x0][y0]=='@':return 0
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if seen[x][y]==1:continue
          if S[x][y]=='@':break
          if d[x][y] < d[x0][y0] + 1: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
#from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[0 for i in range(W)] for j in range(H)]
    todo = []
    if S[x0][y0]=='@':return 0
    seen[x0][y0] = 1
    todo.append(x0*W+y0)
    for X in todo:
      x0,y0 = divmod(X,W)
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if seen[x][y]==1:continue
          if S[x][y]=='@':break
          seen[x][y] = 1
          todo.append(x*W+y)
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans > 0 else -1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[0 for i in range(W)] for j in range(H)]
    todo = deque()
    if S[x0][y0]=='@':return 0
    seen[x0][y0] = 1
    todo.append(x0*W+y0)
    while todo:
      x0,y0 = divmod(todo.popleft(),W)
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if seen[x][y]==1:continue
          if S[x][y]=='@':break
          seen[x][y] = 1
          todo.append(x*W+y)
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans > 0 else -1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[0 for i in range(W)] for j in range(H)]
    todo = deque()
    if S[x0][y0]=='@':return 0
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if seen[x][y]==1:continue
          if S[x][y]=='@':break
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans > 0 else -1)
  
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())
start = (x1-1,y1-1);goal = (x2-1,y2-1)
S=[list(input()) for _ in range(H)]

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  d = [[0 for i in range(W)] for j in range(H)]
  todo = deque()
  now = s
  if S[now[0]][now[1]]=='@':return 0
  seen[now[0]][now[1]] = 1
  todo.append(now)
  while todo:
    now = todo.popleft()
    dx,dy = (1,-1,0,0),(0,0,1,-1)
    for i in range(4):
      for k in range(K):
        new = (now[0]+dx[i]*(k+1), now[1]+dy[i]*(k+1))
        if new[0]<0 or new[0]>=H:break
        if new[1]<0 or new[1]>=W:break
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='@':break
        seen[new[0]][new[1]] = 1
        todo.append(new)
        d[new[0]][new[1]] = d[now[0]][now[1]] + 1
  return d

d = bfs(start)
print(d[goal[0]][goal[1]] if d[goal[0]][goal[1]] > 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
start = (x1-1,y1-1);goal = (x2-1,y2-1)
S=[input() for _ in range(H)]

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  d = [[0 for i in range(W)] for j in range(H)]
  todo = deque()
  now = s
  if S[now[0]][now[1]]=='@':return 0
  seen[now[0]][now[1]] = 1
  todo.append(now)
  while todo:
    now = todo.popleft()
    dx,dy = (1,-1,0,0),(0,0,1,-1)
    for i in range(4):
      for k in range(K):
        new = (now[0]+dx[i]*(k+1), now[1]+dy[i]*(k+1))
        if new[0]<0 or new[0]>=H:break
        if new[1]<0 or new[1]>=W:break
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='@':break
        seen[new[0]][new[1]] = 1
        todo.append(new)
        d[new[0]][new[1]] = d[now[0]][now[1]] + 1
  return d

d = bfs(start)
print(d[goal[0]][goal[1]] if d[goal[0]][goal[1]] > 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
start = (x1-1,y1-1);goal = (x2-1,y2-1)
S=[input() for _ in range(H)]

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  d = [[0 for i in range(W)] for j in range(H)]
  todo = deque()
  now = s
  if S[now[0]][now[1]]=='@':return 0
  seen[now[0]][now[1]] = 1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    dx,dy = (1,-1,0,0),(0,0,1,-1)
    for i in range(4):
      for k in range(K):
        new = (now[0]+dx[i]*(k+1), now[1]+dy[i]*(k+1))
        if new[0]<0 or new[0]>=H:break
        if new[1]<0 or new[1]>=W:break
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='@':break
        seen[new[0]][new[1]] = 1
        todo.append(new)
        d[new[0]][new[1]] = d[now[0]][now[1]] + 1
  return d

d = bfs(start)
print(d[goal[0]][goal[1]] if d[goal[0]][goal[1]] > 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline

H, W, K = map(int,input().split())
D = 4
xs, ys, xt, yt = map(int,input().split())
xs -= 1
ys -= 1
xt -= 1
yt -= 1

G = [input() for _ in range(H)]

def convert(x, y, d):
  return (x * W + y) * D + d
def convert_inv(p):
  x = p // (W*D)
  y = (p - x * (W*D)) // D
  d = (p - x * (W*D) - y * D)
  return [x, y, d]

def convert_cost(times, hist):
  return times * (K+1) + hist
def convert_cost_inv(c):
  return [c//(K+1), c%(K+1)]
  

def is_possible(x, y):
  return 0 <= x <= H-1 and 0 <= y <= W-1 and G[x][y] == "."

task = [(convert_cost(1, 0), convert(xs, ys, d)) for d in range(D)]
visited = set()
pt_0 = convert(xt, yt, 0)
dp = [(1,0), (-1,0), (0,1), (0,-1)]

while task:
  while task:
    c, p = heappop(task)
    if p not in visited:
      break
    if not task:
      print(-1)
      sys.exit()
  if pt_0 <= p <= pt_0+D-1:
    print(convert_cost_inv(c)[0])
    sys.exit()
  visited.add(p)
  x, y, d = convert_inv(p)
  c_t, c_h = convert_cost_inv(c)
  
  #向き変更
  for d_n in range(D):
    p_n = convert(x, y, d_n)
    if p_n not in visited:
      heappush(task, (convert_cost(c_t+1, 0), p_n))
     
  #直進
  dx, dy = dp[d]
  if is_possible(x+dx, y+dy):
    #print(x, y, d, c, dx, dy)
    p_n = convert(x+dx, y+dy, d)
    if p_n not in visited:
      if c_h < K:
        heappush(task, (convert_cost(c_t, c_h+1), p_n))
      else:
        heappush(task, (convert_cost(c_t+1, 1), p_n))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline

H, W, K = map(int,input().split())
D = 4
xs, ys, xt, yt = map(int,input().split())
xs -= 1
ys -= 1
xt -= 1
yt -= 1

G = [input() for _ in range(H)]

def convert(x, y, d):
  return (x * W + y) * D + d
def convert_inv(p):
  x = p // (W*D)
  y = (p - x * (W*D)) // D
  d = (p - x * (W*D) - y * D)
  return (x, y, d)

def convert_cost(times, hist):
  return times * (K+1) + hist
def convert_cost_inv(c):
  return (c//(K+1), c%(K+1))
  

def is_possible(x, y):
  return 0 <= x <= H-1 and 0 <= y <= W-1 and G[x][y] == "."

task = [(convert_cost(1, 0), convert(xs, ys, d)) for d in range(D)]
visited = set()
pt_0 = convert(xt, yt, 0)
dp = [(1,0), (-1,0), (0,1), (0,-1)]

while task:
  while task:
    c, p = heappop(task)
    if p not in visited:
      break
    if not task:
      print(-1)
      sys.exit()
  if pt_0 <= p <= pt_0+D-1:
    print(convert_cost_inv(c)[0])
    sys.exit()
  visited.add(p)
  x, y, d = convert_inv(p)
  c_t, c_h = convert_cost_inv(c)
  
  #向き変更
  for d_n in range(D):
    p_n = convert(x, y, d_n)
    if p_n not in visited:
      heappush(task, (convert_cost(c_t+1, 0), p_n))
     
  #直進
  dx, dy = dp[d]
  if is_possible(x+dx, y+dy):
    #print(x, y, d, c, dx, dy)
    p_n = convert(x+dx, y+dy, d)
    if p_n not in visited:
      if c_h < K:
        heappush(task, (convert_cost(c_t, c_h+1), p_n))
      else:
        heappush(task, (convert_cost(c_t+1, 1), p_n))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline

H, W, K = map(int,input().split())
D = 4
xs, ys, xt, yt = map(int,input().split())
xs -= 1
ys -= 1
xt -= 1
yt -= 1

G = [input() for _ in range(H)]

def convert(x, y, d):
  return (x * W + y) * D + d
def convert_inv(p):
  x = p // (W*D)
  y = (p - x * (W*D)) // D
  d = (p - x * (W*D) - y * D)
  return (x, y, d)

def is_possible(x, y):
  return 0 <= x <= H-1 and 0 <= y <= W-1 and G[x][y] == "."

task = [((1,0), convert(xs, ys, d)) for d in range(D)]
visited = set()
pt_0 = convert(xt, yt, 0)
dp = [(1,0), (-1,0), (0,1), (0,-1)]

while task:
  while task:
    c, p = heappop(task)
    if p not in visited:
      break
    if not task:
      print(-1)
      sys.exit()
  if pt_0 <= p <= pt_0+D-1:
    print(c[0])
    sys.exit()
  visited.add(p)
  x, y, d = convert_inv(p)
  #向き変更
  for d_n in range(D):
    p_n = convert(x, y, d_n)
    if p_n not in visited:
      heappush(task, ((c[0]+1, 0), p_n))
     
  #直進
  dx, dy = dp[d]
  if is_possible(x+dx, y+dy):
    #print(x, y, d, c, dx, dy)
    p_n = convert(x+dx, y+dy, d)
    if p_n not in visited:
      if c[1] < K:
        heappush(task, ((c[0], c[1]+1), p_n))
      else:
        heappush(task, ((c[0]+1, 1), p_n))

Submission status: Time Limit Exceeded

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

H, W, K = map(int,input().split())
D = 4
xs, ys, xt, yt = map(int,input().split())
xs -= 1
ys -= 1
xt -= 1
yt -= 1

G = [input() for _ in range(H)]

def convert(x, y, d):
  return (x * W + y) * D + d
def convert_inv(p):
  x = p // (W*D)
  y = (p - x * (W*D)) // D
  d = (p - x * (W*D) - y * D)
  return (x, y, d)

def is_possible(x, y):
  return 0 <= x <= H-1 and 0 <= y <= W-1 and G[x][y] == "."

task = [((1,0), convert(xs, ys, d)) for d in range(D)]
visited = set()
pt_0 = convert(xt, yt, 0)
dp = [(1,0), (-1,0), (0,1), (0,-1)]

while task:
  while task:
    c, p = heappop(task)
    if p not in visited:
      break
    if not task:
      print(-1)
      sys.exit()
  if pt_0 <= p <= pt_0+D-1:
    print(c[0])
    sys.exit()
  visited.add(p)
  x, y, d = convert_inv(p)
  #向き変更
  for d_n in range(D):
    p_n = convert(x, y, d_n)
    if p_n not in visited:
      heappush(task, ((c[0]+1, 0), p_n))
     
  #直進
  dx, dy = dp[d]
  if is_possible(x+dx, y+dy):
    #print(x, y, d, c, dx, dy)
    p_n = convert(x+dx, y+dy, d)
    if p_n not in visited:
      if c[1] < K:
        heappush(task, ((c[0], c[1]+1), p_n))
      else:
        heappush(task, ((c[0]+1, 1), p_n))

Submission status: Time Limit Exceeded

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

H,W,K = map(int,readline().split())
sy,sx,gy,gx = map(lambda x:int(x) - 1,readline().split())

INF = 10 ** 6

C = [None] * H
for i in range(H):
  C[i] = readline().rstrip()

import heapq as hq
q = []
hq.heapify(q)

# 上、右、下、左
cases = ((-1,0),(0,1),(1,0),(0,-1))

# dist[h][w][方角]
dist = [[[INF] * 4 for j in range(W)] for i in range(H)]

import math
from decimal import Decimal

q.append((Decimal(0), sy, sx, 0))

# di = 0:上、1:右、2:下、3:左
while q:
  cost, y, x, di = hq.heappop(q)
  if dist[y][x][di] <= cost:
    continue
  dist[y][x][di] = cost
  if C[y][x] == "@":
    continue
  if y == gy and x == gx:
    print(math.ceil(cost))
    break
  # 今の向きのまま進む
  if 0 <= y + cases[di][0] < H and 0 <= x + cases[di][1] < W:
    hq.heappush(q, (cost + Decimal(1) / Decimal(K), y + cases[di][0], x + cases[di][1], di))
    
  # 方向転換する
  hq.heappush(q, (math.ceil(cost), y, x, (di + 1) % 4))
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())

cmat=[[x=="." for x in input()] for _ in range(H)]
#print(cmat)

from collections import defaultdict
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist,prev={},{}
  used=set()
  for v in vlist:
    dist[v]=float("inf")
    prev[v]=-1
  dist[s]=0
  used.add(s)

  hq_edge=[]
  for v,w in graph[s]:
    if w=="step":
      heapq.heappush(hq_edge,(1/K,v,s))
    elif w=="turn":
      heapq.heappush(hq_edge,(0,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if min_v in used:
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used.add(min_v)
    for v,w in graph[min_v]:
      if not v in used:
        if w=="step":
          heapq.heappush(hq_edge,(min_w+1/K,v,min_v))
        elif w=="turn":
          heapq.heappush(hq_edge,(math.ceil(min_w),v,min_v))

  return dist,prev

vlist=[]
for i in range(H):
  for j in range(W):
    if cmat[i][j]:
      vlist.append((i,j,"L"))
      vlist.append((i,j,"R"))
      vlist.append((i,j,"U"))
      vlist.append((i,j,"D"))
      
graph=defaultdict(list)
for i in range(H):
  for j in range(W):
    if cmat[i][j]:
      graph[(i,j,"L")].append([(i,j,"U"),"turn"])
      graph[(i,j,"L")].append([(i,j,"D"),"turn"])
      graph[(i,j,"R")].append([(i,j,"U"),"turn"])
      graph[(i,j,"R")].append([(i,j,"D"),"turn"])
      graph[(i,j,"U")].append([(i,j,"L"),"turn"])
      graph[(i,j,"U")].append([(i,j,"R"),"turn"])
      graph[(i,j,"D")].append([(i,j,"L"),"turn"])
      graph[(i,j,"D")].append([(i,j,"R"),"turn"])
      
    if i>0 and cmat[i-1][j]:
      graph[(i,j,"U")].append([(i-1,j,"U"),"step"])
    if i<H-1 and cmat[i+1][j]:
      graph[(i,j,"D")].append([(i+1,j,"D"),"step"])
    if j>0 and cmat[i][j-1]:
      graph[(i,j,"L")].append([(i,j-1,"L"),"step"])
    if j<W-1 and cmat[i][j+1]:
      graph[(i,j,"R")].append([(i,j+1,"R"),"step"])
      
#print(vlist)
#print(graph)

dist,prev=dijkstra_heap((x1-1,y1-1,"L"))
answer=max(dist[(x2-1,y2-1,"U")],dist[(x2-1,y2-1,"D")],dist[(x2-1,y2-1,"L")],dist[(x2-1,y2-1,"R")])

if answer==float("inf"):
  print(-1)
else:
  print(answer)

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())
inf=float("inf")

C=["*"*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    S=input()
    C[i]="*"+S+"*"

T=[[[inf,inf,inf,inf] for __ in range(W+2)] for _ in range(H+2)] #(0,1,2,3)→(下,上,右,左)
T[X1][Y1][0]=T[X1][Y1][1]=T[X1][Y1][2]=T[X1][Y1][3]=0

Q=deque([(X1,Y1,0),(X1,Y1,1),(X1,Y1,2),(X1,Y1,3)])
V=[(1,0),(-1,0),(0,1),(0,-1)]

while Q:
    A,B,D=Q.popleft()

    u,v=V[D]

    #移動
    if C[A+u][B+v]=="." and T[A+u][B+v][D]>T[A][B][D]+1:
        T[A+u][B+v][D]=T[A][B][D]+1
        Q.append((A+u,B+v,D))

    #方向転換
    for d in range(4):
        if T[A][B][d]>((T[A][B][D]+(K-1))//K)*K:
            T[A][B][d]=((T[A][B][D]+(K-1))//K)*K
            Q.append((A,B,d))


if min(T[X2][Y2])<inf:
    U=min(T[X2][Y2])
    print((U+(K-1))//K)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W,K=map(int,input().split())
X1,Y1,X2,Y2=map(int,input().split())
inf=float("inf")

Rest=H*W-1
C=["*"*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    S=input()
    C[i]="*"+S+"*"
    Rest-=S.count("@")

T=[[inf]*(W+2) for _ in range(H+2)]
T[X1][Y1]=0

Q=deque([(X1,Y1)])
V=[(1,0),(0,1),(-1,0),(0,-1)]
while Q and Rest>0:
    A,B=Q.popleft()

    for (u,v) in V:
        E=A
        F=B
        for _ in range(K):
            E+=u
            F+=v

            if C[E][F]==".":
                if T[E][F]==inf:
                    T[E][F]=T[A][B]+1
                    Q.append((E,F))
                    Rest-=1
            else:
                break

if T[X2][Y2]<inf:
    print(T[X2][Y2])
else:
    print(-1)

Submission status: Time Limit Exceeded

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

def main():
  h, w, k = map(int, input().split())
  y1, x1, y2, x2 = map(int, input().split())
  x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1;
  graph = []
  dist = [[None]*w for _ in range(h)]

  for i in range(h):
    row = [0 if s == '.' else 1 for s in input()]
    graph.append(row)

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

  while stack:
    x, y = stack.popleft()
    d = dist[y][x]
    # 西に進むとき
    for i in range(1, k+1):
      if x-i >= 0 and graph[y][x-i] == 0:
        if dist[y][x-i] is None:
          dist[y][x-i] = d + 1
          if x-i == x2 and y == y2:
            print(d+1)
            return
          stack.append([x-i, y])
      else:
        break
    # 東に進むとき
    for i in range(1, k+1):
      if x+i <= w-1 and graph[y][x+i] == 0:
        if dist[y][x+i] is None:
          dist[y][x+i] = d + 1
          if x+i == x2 and y == y2:
            print(d+1)
            return
          stack.append([x+i, y])
      else:
        break

    # 北に進むとき
    for i in range(1, k+1):
      if y-i >= 0 and graph[y-i][x] == 0:
        if dist[y-i][x] is None:
          dist[y-i][x] = d + 1
          if x == x2 and y-i == y2:
            print(d+1)
            return
          stack.append([x, y-i])
      else:
        break

    # 東に進むとき
    for i in range(1, k+1):
      if y+i <= h-1 and graph[y+i][x] == 0:
        if dist[y+i][x] is None:
          dist[y+i][x] = d + 1
          if x == x2 and y+i == y2:
            print(d+1)
            return
          stack.append([x, y+i])
      else:
        break
        
  print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  h, w, k = map(int, input().split())
  y1, x1, y2, x2 = map(int, input().split())
  x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1;
  graph = []
  dist = [[None]*w for _ in range(h)]

  for i in range(h):
    row = [0 if s == '.' else 1 for s in input()]
    graph.append(row)

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

  while stack:
    x, y = stack.popleft()
    d = dist[y][x]
    # 西に進むとき
    for i in range(1, k+1):
      if x-i >= 0 and graph[y][x-i] == 0:
        if dist[y][x-i] is None:
          dist[y][x-i] = d + 1
          if x-i == x2 and y == y2:
            print(d+1)
            return
          stack.append([x-i, y])
      else:
        break
    # 東に進むとき
    for i in range(1, k+1):
      if x+i <= w-1 and graph[y][x+i] == 0:
        if dist[y][x+i] is None:
          dist[y][x+i] = d + 1
          if x+i == x2 and y == y2:
            print(d+1)
            return
          stack.append([x+i, y])
      else:
        break

    # 北に進むとき
    for i in range(1, k+1):
      if y-i >= 0 and graph[y-i][x] == 0:
        if dist[y-i][x] is None:
          dist[y-i][x] = d + 1
          if x == x2 and y-i == y2:
            print(d+1)
            return
          stack.append([x, y-i])
      else:
        break

    # 東に進むとき
    for i in range(1, k+1):
      if y+i <= h-1 and graph[y+i][x] == 0:
        if dist[y+i][x] is None:
          dist[y+i][x] = d + 1
          if x == x2 and y+i == y2:
            print(d+1)
            return
          stack.append([x, y+i])
      else:
        break
        
  print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  h, w, k = map(int, input().split())
  y1, x1, y2, x2 = map(int, input().split())
  x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1;
  graph = []
  dist = [[None]*w for _ in range(h)]

  for i in range(h):
    row = list(input())
    graph.append(row)

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

  while stack:
    x, y = stack.popleft()
    d = dist[y][x]
    # 西に進むとき
    for i in range(1, k+1):
      if x-i >= 0 and graph[y][x-i] == '.':
        if dist[y][x-i] is None:
          dist[y][x-i] = d + 1
          if x-i == x2 and y == y2:
            print(d+1)
            return
          stack.append([x-i, y])
      else:
        break
    # 東に進むとき
    for i in range(1, k+1):
      if x+i <= w-1 and graph[y][x+i] == '.':
        if dist[y][x+i] is None:
          dist[y][x+i] = d + 1
          if x+i == x2 and y == y2:
            print(d+1)
            return
          stack.append([x+i, y])
      else:
        break

    # 北に進むとき
    for i in range(1, k+1):
      if y-i >= 0 and graph[y-i][x] == '.':
        if dist[y-i][x] is None:
          dist[y-i][x] = d + 1
          if x == x2 and y-i == y2:
            print(d+1)
            return
          stack.append([x, y-i])
      else:
        break

    # 東に進むとき
    for i in range(1, k+1):
      if y+i <= h-1 and graph[y+i][x] == '.':
        if dist[y+i][x] is None:
          dist[y+i][x] = d + 1
          if x == x2 and y+i == y2:
            print(d+1)
            return
          stack.append([x, y+i])
      else:
        break
        
  print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    #d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        m,x,y =  heapq.heappop(q)
        if d[x][y] <= m: continue
        d[x][y] = m
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < d[x][y] + 1: break
                if d[nx][ny] == d[x][y] + 1: continue
                #d[nx][ny] = d[x][y] + 1
                q.append((m+1,nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    for i in range(4):
        d[x1][y1] = 0

    q = collections.deque()
    q.append((x1,y1))
    while q:
        x,y = q.pop()
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] <= d[x][y] + 1: break
                if d[nx][ny] == d[x][y] + 1: continue
                d[nx][ny] = d[x][y] + 1
                q.append((nx,ny))
    if d[x2][y2] < float('inf'):
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    for i in range(4):
        d[x1][y1] = 0

    q = collections.deque()
    q.append((x1,y1))
    while q:
        x,y = q.pop()
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < d[x][y] + 1: break
                if d[nx][ny] == d[x][y] + 1: continue
                d[nx][ny] = d[x][y] + 1
                q.append((nx,ny))
    if d[x2][y2] < float('inf'):
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    for i in range(4):
        d[x1][y1] = 0

    q = collections.deque()
    q.append((x1,y1))
    while q:
        x,y = q.pop()
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] <= d[x][y] + 1: continue
                d[nx][ny] = d[x][y] + 1
                q.append((nx,ny))
    if d[x2][y2] < float('inf'):
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()