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: Accepted

Solution code:
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        # divisors.sort()
        return divisors
    N = I()
    A = LI()
    C = set()
    n = 10**6+1
    D = [False]*n
    ans = 0
    for a in A:
        if a in D:
            D[a] = False
            continue
        D[a] = True
        C.add(a)

    for a in C:
        for i in range(2,1+n//a):
            D[i*a] = False
    ans = sum(D)
    print(ans)
    return

def examE():
    N, Q = LI()
    AB = [LI()for _ in range(N)]



    ans = 0
    print(ans)
    return

def examF():
    H, W, K = LI()
    x1,y1,x2,y2 = LI()
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    C = [SI()for _ in range(H)]

    def bfs_grid(h, w, s, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue_up = deque()
            queue_d = deque()
            queue_r = deque()
            queue_l = deque()
            queue_up.append(s)
            queue_d.append(s)
            queue_r.append(s)
            queue_l.append(s)
            distance[s[0]][s[1]] = 0
            while (len(queue_up) or len(queue_r) or len(queue_d) or len(queue_l)):
                if queue_up:
                    y, x = queue_up.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y + k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_up.append((ny, nx))
                if queue_d:
                    y, x = queue_d.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y - k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_d.append((ny, nx))
                if queue_r:
                    y, x = queue_r.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x + k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_r.append((ny, nx))
                if queue_l:
                    y, x = queue_l.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x - k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_l.append((ny, nx))

            return distance

        return bfsg()
    L = bfs_grid(H,W,(x1,y1),C)
    #print(L)
    ans = L[x2][y2]
    if ans==inf:
        ans = -1
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      p = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        for k in range(1, K + 1):
          hh = h + i * k
          ww = w + j * k
          if s.L[hh + 1][ww + 1] >= 0:
            if T[hh][ww] == -1 or T[hh][ww] > p + 1:
              q.put([hh, ww])
              T[hh][ww] = p + 1
            elif T[hh][ww] != p + 1:
              break
          else:
            break
            
    return T, k


H, W, K = list(map(int, input().split()))
xy = list(map(int, input().split()))
c = []
for i in range(H):
  c.append(list(input().replace("\n", "")))

for i in range(H):
  for j in range(W):
    if c[i][j] == ".":
      c[i][j] = 0
    else:
      c[i][j] = -1

g = gridMan(c)
g.makeWall()

L, k = g.dist([xy[0] - 1, xy[1] - 1])

print(L[xy[2] - 1][xy[3] - 1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(100000)

h,w,k = map(int,input().split())
y1,x1,y2,x2 = map(int,input().split())
grid = []
grid.append(['@']*(w+2))
for i in range(h):
    grid.append(['@']+list(input())+['@'])
grid.append(['@']*(w+2))

q = set()
next_q = set()
next_q.add((y1,x1))
ans = 0
while True:
    if not next_q:
        print(-1)
        exit()
    for y,x in next_q:
        grid[y][x] = '@'
    q = next_q
    next_q = set()
    while q:
        y,x = q.pop()
        if (y,x) == (y2,x2):
            print(ans)
            exit()
        for i in range(1,k+1):
            if grid[y+i][x] == '@':
                break
            next_q.add((y+i,x))
        for i in range(1,k+1):
            if grid[y-i][x] == '@':
                break
            next_q.add((y-i,x))
        for i in range(1,k+1):
            if grid[y][x+i] == '@':
                break
            next_q.add((y,x+i))
        for i in range(1,k+1):
            if grid[y][x-i] == '@':
                break
            next_q.add((y,x-i))
    ans += 1

Submission status: Runtime Error

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()
    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 d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y] = 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: Runtime Error

Solution code:
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
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]

ans = bfs(x1,y1,x2,y2)
print(ans if ans > 0 else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
G=[["@"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["@"]+list(input())+["@"]
V=[[10**10]*(w+2) for i in range(h+2)]
V[sy][sx]=0
D=[[[0,0,0,0] for j in range(w+2)] for i in range(h+2)]
D[sy][sx]=[1,1,1,1]
X=deque([])
Y=deque([])
i=1
while G[sy-i][sx]==".":
  Y.append(sy-i)
  X.append(sx)
  V[sy-i][sx]=1
  D[sy-i][sx][0]=1
  D[sy-i][sx][1]=1
  if i==k:
    D[sy-i][sx][0]=0
    break
  i=i+1
i=1
while G[sy+i][sx]==".":
  Y.append(sy+i)
  X.append(sx)
  V[sy+i][sx]=1
  D[sy+i][sx][0]=1
  D[sy-i][sx][1]=1
  if i==k:
    D[sy+i][sx][1]=0
    break
  i=i+1

i=1
while G[sy][sx-i]==".":
  Y.append(sy)
  X.append(sx-i)
  V[sy][sx-i]=1
  D[sy][sx-i][2]=1
  D[sy-i][sx][3]=1
  if i==k:
    D[sy][sx-i][2]=0
    break
  i=i+1
i=1
while G[sy][sx+i]==".":
  Y.append(sy)
  X.append(sx+i)
  V[sy][sx+i]=1
  D[sy][sx+i][2]=1
  D[sy-i][sx][3]=1
  if i==k:
    D[sy][sx+i][3]=0
    break
  i=i+1

def yn(yy,xx):
  D[yy][xx][0]=1
  i=1
  while G[yy-i][xx]==".":
    D[yy-i][xx][0]=1
    D[yy-i][xx][1]=1
    V[yy-i][xx]=min(V[yy-i][xx],V[yy][xx]+1)
    if i==k:
      D[yy-i][xx][0]=0
      Y.append(yy-i)
      X.append(xx)
      break
    if D[yy-i][xx]!=[1,1,1,1]:
      Y.append(yy-i)
      X.append(xx)
    i=i+1


def yp(yy,xx):
  D[yy][xx][1]=1
  i=1
  while G[yy+i][xx]==".":
    D[yy+i][xx][0]=1
    D[yy+i][xx][1]=1
    V[yy+i][xx]=min(V[yy+i][xx],V[yy][xx]+1)
    if i==k:
      D[yy+i][xx][1]=0
      Y.append(yy+i)
      X.append(xx)
      break
    if D[yy+i][xx]!=[1,1,1,1]:
      Y.append(yy+i)
      X.append(xx)
    i=i+1


def xn(yy,xx):
  D[yy][xx][2]=1
  i=1
  while G[yy][xx-i]==".":
    D[yy][xx-i][2]=1
    D[yy][xx-i][3]=1
    V[yy][xx-i]=min(V[yy][xx-i],V[yy][xx]+1)
    if i==k:
      D[yy][xx-i][2]=0
      Y.append(yy)
      X.append(xx-i)
      break
    if D[yy][xx-i]!=[1,1,1,1]:
      Y.append(yy)
      X.append(xx-i)
    i=i+1


def xp(yy,xx):
  D[yy][xx][3]=1
  i=1
  while G[yy][xx+i]==".":
    D[yy][xx+i][2]=1
    D[yy][xx+i][3]=1
    V[yy][xx+i]=min(V[yy][xx+i],V[yy][xx]+1)
    if i==k:
      D[yy][xx+i][3]=0
      Y.append(yy)
      X.append(xx+i)
      break
    if D[yy][xx+i]!=[1,1,1,1]:
      Y.append(yy)
      X.append(xx+i)
    i=i+1



while len(X)>0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  if D[y][x][0]==0:
    yn(y,x)
  if D[y][x][1]==0:
    yp(y,x)
  if D[y][x][2]==0:
    xn(y,x)
  if D[y][x][3]==0:
    xp(y,x)
  
if V[gy][gx]==10**10:
  print(-1)
else:
  print(V[gy][gx])

Submission status: Runtime Error

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


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[[INF] * w for _ in range(h)] for _ in range(4)]
    dist[U][i1][j1] = 0
    q = deque([(0, U, i1, j1)])
    while q:
        d, dire, i, j = q.popleft()

        for cnt in range(1, 4):
            if d < dist[(dire + cnt) % 4][i][j]:
                dist[(dire + cnt) % 4][i][j] = d
                q.appendleft((d, (dire + cnt) % 4, i, j))

        if dire == U:
            for length in range(1, k + 1):
                nxt_i = i - length
                if 0 <= nxt_i and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == D:
            for length in range(1, k + 1):
                nxt_i = i + length
                if nxt_i < h and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == L:
            for length in range(1, k + 1):
                nxt_j = j - length
                if 0 <= nxt_j and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][i][nxt_j], dire, i, nxt_j))
                else:
                    break
        if dire == R:
            for length in range(1, k + 1):
                nxt_j = j + length
                if nxt_j < w and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][i][nxt_j], dire, i, nxt_j))
                else:
                    break

    return dist


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


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = min([dist[i][x2][y2] for i in range(4)])

if ans == 10 ** 18:
    print(re)
else:
    print(ans)

Submission status: Runtime Error

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


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[[INF] * w for _ in range(h)] for _ in range(4)]
    dist[U][i1][j1] = 0
    q = deque([(0, U, i1, j1)])
    while q:
        d, dire, i, j = q.popleft()
        if dist[dire][i][j] < d:
            continue
        for cnt in range(1, 4):
            if d < dist[(dire + cnt) % 4][i][j]:
                dist[(dire + cnt) % 4][i][j] = d
                q.appendleft((d, (dire + cnt) % 4, i, j))

        if dire == U:
            for length in range(1, k + 1):
                nxt_i = i - length
                if 0 <= nxt_i and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == D:
            for length in range(1, k + 1):
                nxt_i = i + length
                if nxt_i < h and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == L:
            for length in range(1, k + 1):
                nxt_j = j - length
                if 0 <= nxt_j and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][i][nxt_j], dire, i, nxt_j))
                else:
                    break
        if dire == R:
            for length in range(1, k + 1):
                nxt_j = j + length
                if nxt_j < w and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][i][nxt_j], dire, i, nxt_j))
                else:
                    break

    return dist


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


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = min([dist[i][x2][y2] for i in range(4)])

if ans == 10 ** 18:
    print(re)
else:
    print(ans)

Submission status: Runtime Error

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


def dijkstra(i1, j1) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 9
    dist = [[[INF] * w for _ in range(h)] for _ in range(4)]
    dist[U][i1][j1] = 0
    q = deque([(0, U, i1, j1)])   # q = [(startからの距離, 現在地)]
    while q:
        d, dire, i, j = q.popleft()
        if dist[dire][i][j] < d:
            continue
        for cnt in range(1, 4):
            if dist[dire][i][j] < dist[(dire + cnt) % 4][i][j]:
                dist[(dire + cnt) % 4][i][j] = dist[dire][i][j]
                q.appendleft((dist[dire][i][j], (dire + cnt) % 4, i, j))
        if dire == U:
            for length in range(1, k + 1):
                nxt_i = i - length
                if 0 <= nxt_i and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == D:
            for length in range(1, k + 1):
                nxt_i = i + length
                if nxt_i < h and c[nxt_i][j] == "." and dist[dire][i][j] + 1 < dist[dire][nxt_i][j]:
                    dist[dire][nxt_i][j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, nxt_i, j))
                else:
                    break
        if dire == L:
            for length in range(1, k + 1):
                nxt_j = j - length
                if 0 <= nxt_j and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, i, nxt_j))
                else:
                    break
        if dire == R:
            for length in range(1, k + 1):
                nxt_j = j + length
                if nxt_j < w and c[i][nxt_j] == "." and dist[dire][i][j] + 1 < dist[dire][i][nxt_j]:
                    dist[dire][i][nxt_j] = dist[dire][i][j] + 1
                    q.append((dist[dire][nxt_i][j], dire, i, nxt_j))
                else:
                    break

    return dist


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


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = dijkstra(x1, y1)
ans = min([dist[i][x2][y2] for i in range(4)])

if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y ==dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            K -= 1
            nx += dx[i]
            ny += dy[i]
        if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[nx][ny] != "@" and depth[nx][ny] > depth[y][x]:
            if depth[ny][nx] == depth[y][x]+1:
                continue
            depth[ny][nx] = depth[y][x] +1
            dq.append((nx,ny))
        else:
            break
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
  x,y ==dq.popleft()
  if x == d and y == c:
    break
  for i in range(4):
    nx,ny,K = x,y,k
    while K:
      K -= 1
      nx += dx[i]
      ny += dy[i]
      if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[nx][ny] != "@" and depth[nx][ny] > depth[y][x]:
        if depth[ny][nx] == depth[y][x]+1:
          continue
        depth[ny][nx] = depth[y][x] +1
        dq.append((nx,ny))
      else:
        break
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d=map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
  x,y ==dq.popleft()
  if x == d and y == c:
    break
  for i in range(4):
    nx,ny,K = x,y,k
    while K:
      K -= 1
      nx += dx[i]
      ny += dy[i]
      if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[nx][ny] != "@" and depth[nx][ny] > depth[y][x]:
        if depth[ny][nx] == depth[y][x]+1:
          continue
        depth[ny][nx] = depth[y][x] +1
        dq.append((nx,ny))
      else:
        break
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d=map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0 1, -1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([b,a])
depth[a][b] = 0
while dq:
  x,y ==dq.popleft()
  if x == d and y == c:
    break
  for i in range(4):
    nx,ny,K = x,y,k
    while K:
      K -= 1
      nx += dx[i]
      ny += dy[i]
      if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[nx][ny] != "@" and depth[nx][ny] > depth[y][x]:
        if depth[ny][nx] == depth[y][x]+1:
          continue
        depth[ny][nx] = depth[y][x] +1
        dq.append((nx,ny))
      else:
        break
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Runtime Error

Solution code:
import sys
def main():
    input = sys.stdin.readline
    Dy = [0,1,0,-1]
    Dx = [1,0,-1,0]
    H, W, K = map(int, input().split())
    y1,x1,y2,x2 = map(int, input().split())
    C = ["@" + input() for _ in range(H)]
    C = ["@"*(W+2)] + C + ["@"*(W+2)]
    Closed = [[False]*(W+2) for _ in range(H+2)]
    Nexts = [[[(y+dy, x+dx) for x in range(W+2)] for y in range(H+2)] for dy, dx in zip(Dy, Dx)]
    def root(y, x, Next):
        yp, xp = Next[y][x]
        if not Closed[yp][xp]:
            return yp, xp
        else:
            yp, xp = root(yp, xp, Next)
            Next[y][x] = (yp, xp)
            return yp, xp
    def remove(y, x):
        for i in range(2):
            y1, x1 = Nexts[i][y][x]
            y2, x2 = Nexts[i+2][y][x]
            Nexts[i+2][y1][x1] = (y2, x2)
            Nexts[i][y2][x2] = (y1, x1)
        Closed[y][x] = True
    q = [(y1, x1)]
    remove(y1, x1)
    ans = 0
    while q:
        q_new = []
        for y0, x0 in q:
            if (y0, x0) == (y2, x2):
                print(ans)
                exit()
            for Next in Nexts:
                while True:
                    y, x = root(y0, x0, Next)
                    if abs(y-y0)+abs(x-x0) > K or C[y][x] != ".":
                        break
                    remove(y, x)
                    q_new.append((y, x))
        q = q_new
        ans += 1
    print(-1)

main()

Submission status: Runtime Error

Solution code:
def main():
    input = sys.stdin.readline
    Dy = [0,1,0,-1]
    Dx = [1,0,-1,0]
    H, W, K = map(int, input().split())
    y1,x1,y2,x2 = map(int, input().split())
    C = ["@" + input() for _ in range(H)]
    C = ["@"*(W+2)] + C + ["@"*(W+2)]
    Closed = [[False]*(W+2) for _ in range(H+2)]
    Nexts = [[[(y+dy, x+dx) for x in range(W+2)] for y in range(H+2)] for dy, dx in zip(Dy, Dx)]
    def root(y, x, Next):
        yp, xp = Next[y][x]
        if not Closed[yp][xp]:
            return yp, xp
        else:
            yp, xp = root(yp, xp, Next)
            Next[y][x] = (yp, xp)
            return yp, xp
    def remove(y, x):
        for i in range(2):
            y1, x1 = Nexts[i][y][x]
            y2, x2 = Nexts[i+2][y][x]
            Nexts[i+2][y1][x1] = (y2, x2)
            Nexts[i][y2][x2] = (y1, x1)
        Closed[y][x] = True
    q = [(y1, x1)]
    remove(y1, x1)
    ans = 0
    while q:
        q_new = []
        for y0, x0 in q:
            if (y0, x0) == (y2, x2):
                print(ans)
                exit()
            for Next in Nexts:
                while True:
                    y, x = root(y0, x0, Next)
                    if abs(y-y0)+abs(x-x0) > K or C[y][x] != ".":
                        break
                    remove(y, x)
                    q_new.append((y, x))
        q = q_new
        ans += 1
    print(-1)

main()

Submission status: Runtime Error

Solution code:
def main():
    input = sys.stdin.readline
    Dy = [0,1,0,-1]
    Dx = [1,0,-1,0]
    H, W, K = map(int, input().split())
    y1,x1,y2,x2 = map(int, input().split())
    C = ["@" + input() for _ in range(H)]
    C = ["@"*(W+2)] + C + ["@"*(W+2)]
    Nexts = [[[1]*(W+2) for _ in range(H+2)] for _ in range(4)]
    q = [(y1, x1)]
    ans = 0
    while q:
        q_new = []
        for y0, x0 in q:
            if (y0, x0) == (y2, x2):
                print(ans)
                exit()
            for dy, dx, Next in zip(Dy, Dx, Nexts):
                y, x = y0, x0
                sum_next = 0
                Path = [(y, x)]
                while True:
                    sum_next += Next[y][x]
                    y = y0 + dy * sum_next
                    x = x0 + dx * sum_next
                    if sum_next > K or C[y][x] != ".":
                        break
                    Path.append((y, x))
                    q_new.append((y, x))
                for path_y, path_x in Path:
                    Next[path_y][path_x] = abs(path_y-y) + abs(path_x-x)
        q = q_new
        ans += 1
    print(-1)

main()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def dijkstra():
        inf = 10 ** 9
        visited = [[False]*(w+2) for _ in range(h+2)]

        dp = [[inf]*(w+2) for _ in range(h+2)]
        dp[xs][ys] = 0

        que = [(0, xs, ys, 0)]
        direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        while que:
            cost, x, y, dirt = heappop(que)
            # if (x, y) == (xg, yg):
            #     ans = (dp[x][y] + k - 1)//k
            #     return ans

            if not visited[x][y]:
                for i in range(4):
                    nx, ny = x + direction[i][0], y + direction[i][1]
                    if field[nx][ny]:
                        if i == dirt:
                            if dp[nx][ny] > dp[x][y] + 1:
                                dp[nx][ny] = dp[x][y] + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                        else:
                            if dp[nx][ny] > (dp[x][y] + k-1)//k*k + 1:
                                dp[nx][ny] = (dp[x][y] + k-1)//k*k + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                visited[x][y] = True
        if dp[xg][yg] == inf
            return -1
        else:
            return (dp[xg][yg] + k - 1)//k


    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()