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: Wrong Answer

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

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            else:
                break
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)

Submission status: Wrong Answer

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

def solve(H,W,K,sy,sx,gy,gx,C):
  q = []
  hq.heapify(q)
  
  # 上、右、下、左
  cases = ((-1,0),(0,1),(1,0),(0,-1))
  
  # dist[h][w][方角]
  dist = [[[(INF,INF)] * 4 for j in range(W)] for i in range(H)]
  
  # (コスト, 今までに何マス進めたか)をキーとするheapq
  # コストが少ないほうが確実に有利で、コストが同じ場合は今までに進んだマス数が少ないほど有利なためこれでソートして良い
  
  for i in range(4):
    hq.heappush(q, ((1, 0), sy, sx, i))
    
  while q:
    cost, y, x, di = hq.heappop(q)
    if C[y][x] == "@":
      continue
    if dist[y][x][di] <= cost:
      continue
    dist[y][x][di] = cost
    if y == gy and x == gx:
      print(cost[0])
      break
    # その方向に進む
    if 0 <= y + cases[di][0] < H and 0 <= x + cases[di][1] < W:
      if cost[1] < K:
        hq.heappush(q, ((cost[0], cost[1] + 1),y + cases[di][0],x + cases[di][1], di))
      else:
        hq.heappush(q, ((cost[0] + 1, 1),y + cases[di][0],x + cases[di][1], di))
    # 方向を変える
    for i in range(3):
      hq.heappush(q, ((cost[0] + 1, 0),y,x,(di + i) % 4))
  else:
    print(-1)

solve(H,W,K,sy,sx,gy,gx,C)

Submission status: Wrong Answer

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())
  
C = [None] * H
for i in range(H):
  C[i] = readline().rstrip()
  
import heapq as hq

def solve(H,W,K,sy,sx,gy,gx,C):
  q = []
  hq.heapify(q)
  
  # 上、右、下、左
  cases = ((-1,0),(0,1),(1,0),(0,-1))
  
  # dist[h][w][方角]
  dist = [[[False] * 4 for j in range(W)] for i in range(H)]
  
  # (コスト, 今までに何マス進めたか)をキーとするheapq
  # コストが少ないほうが確実に有利で、コストが同じ場合は今までに進んだマス数が少ないほど有利なためこれでソートして良い
  
  for i in range(4):
    hq.heappush(q, ((1, 0), sy, sx, i))
    
  while q:
    cost, y, x, di = hq.heappop(q)
    if C[y][x] == "@":
      continue
    if dist[y][x][di]:
      continue
    dist[y][x][di] = True
    if y == gy and x == gx:
      print(cost[0])
      break
    # その方向に進む
    if 0 <= y + cases[di][0] < H and 0 <= x + cases[di][1] < W:
      if cost[1] < K:
        hq.heappush(q, ((cost[0], cost[1] + 1),y + cases[di][0],x + cases[di][1], di))
      else:
        hq.heappush(q, ((cost[0] + 1, 1),y + cases[di][0],x + cases[di][1], di))
    # 方向を変える
    for i in range(3):
      hq.heappush(q, ((cost[0] + 1, 0),y,x,(di + i) % 4))
  else:
    print(-1)

solve(H,W,K,sy,sx,gy,gx,C)

Submission status: Wrong Answer

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 = [[[False] * 4 for j in range(W)] for i in range(H)]

# (コスト, 今までに何マス進めたか)をキーとするheapq
# コストが少ないほうが確実に有利で、コストが同じ場合は今までに進んだマス数が少ないほど有利なためこれでソートして良い

for i in range(4):
  hq.heappush(q, ((1, 0), sy, sx, i))
  
while q:
  cost, y, x, di = hq.heappop(q)
  if C[y][x] == "@":
    continue
  if dist[y][x][di]:
    continue
  dist[y][x][di] = True
  if y == gy and x == gx:
    print(cost[0])
    break
  # その方向に進む
  if 0 <= y + cases[di][0] < H and 0 <= x + cases[di][1] < W:
    if cost[1] < K:
      hq.heappush(q, ((cost[0], cost[1] + 1),y + cases[di][0],x + cases[di][1], di))
    else:
      hq.heappush(q, ((cost[0] + 1, 1),y + cases[di][0],x + cases[di][1], di))
  # 方向を変える
  for i in range(3):
    hq.heappush(q, ((cost[0] + 1, 0),y,x,(di + i) % 4))
else:
  print(-1)

Submission status: Wrong Answer

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 = [[[False] * 4 for j in range(W)] for i in range(H)]

import math

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

# di = 0:上、1:右、2:下、3:左
while q:
  cost, y, x, di = hq.heappop(q)
  if dist[y][x][di]:
    continue
  dist[y][x][di] = True
  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:
    if C[y + cases[di][0]][x + cases[di][1]] == ".":
      hq.heappush(q, (cost + (1 / K), y + cases[di][0], x + cases[di][1], di))
    
  # 方向転換する
  for i in range(3):
    hq.heappush(q, (math.ceil(cost), y, x, (di + i) % 4))
else:
  print(-1)

Submission status: Wrong Answer

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 = [[[False] * 4 for j in range(W)] for i in range(H)]

import math

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

# di = 0:上、1:右、2:下、3:左
while q:
  cost, y, x, di = hq.heappop(q)
  if dist[y][x][di]:
    continue
  dist[y][x][di] = True
  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:
    if C[y + cases[di][0]][x + cases[di][1]] == ".":
      hq.heappush(q, (cost + (1 / K), y + cases[di][0], x + cases[di][1], di))
    
  # 方向転換する
  if ~dist[y][x][(di + 1) % 4]:
    hq.heappush(q, (math.ceil(cost), y, x, (di + 1) % 4))
else:
  print(-1)

Submission status: Wrong Answer

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 = [[[False] * 4 for j in range(W)] for i in range(H)]

import math

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

# di = 0:上、1:右、2:下、3:左
while q:
  cost, y, x, di = hq.heappop(q)
  if dist[y][x][di]:
    continue
  dist[y][x][di] = True
  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:
    if C[y + cases[di][0]][x + cases[di][1]] == ".":
      hq.heappush(q, (cost + (1 / K), y + cases[di][0], x + cases[di][1], di))
    
  # 方向転換する
  if dist[y][x][(di + 1) % 4]:
    continue
  hq.heappush(q, (math.ceil(cost), y, x, (di + 1) % 4))
else:
  print(-1)

Submission status: Wrong Answer

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 = [[[False] * 4 for j in range(W)] for i in range(H)]

import math

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

# di = 0:上、1:右、2:下、3:左
while q:
  cost, y, x, di = hq.heappop(q)
  if dist[y][x][di]:
    continue
  dist[y][x][di] = True
  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:
    if C[y + cases[di][0]][x + cases[di][1]] == ".":
      hq.heappush(q, (cost + (1 / 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: Wrong Answer

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

q.append((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 y == gy and x == gx:
    print(math.ceil(cost))
    break
  # 今の向きのまま進む
  if 0 <= y + cases[di][0] < H and 0 <= x + cases[di][1] < W:
    if C[y + cases[di][0]][x + cases[di][1]] == ".":
      hq.heappush(q, (cost + (1 / 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: Wrong Answer

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

q.append((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 + (1 / 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: Wrong Answer

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 ** 10

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: Wrong Answer

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

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

    sx, sy, gx, gy = map(int, input().split())

    c = [input() for _ in range(h)]
    ans1 = [[-1]*(w+2) for i in range(h+2)]
    ans2 = [[-1]*(w+2) for i in range(h+2)]
    ans3 = [[-1]*(w+2) for i in range(h+2)]
    ans4 = [[-1]*(w+2) for i in range(h+2)]

    already = [[False]*(w+2) for i in range(h+2)]
    for i in range(h+2):
        for j in range(w+2):
            if i == 0 or j == 0 or i == h+1 or j == w+1:
                already[i][j] = True
            else:
                if c[i-1][j-1] == "@":
                    already[i][j] = True

    not_yet = [(0, sx, sy, 1), (0, sx, sy, 2), (0, sx, sy, 3), (0, sx, sy, 4)]

    mod = 10000000
    while not_yet:
        cost, x, y, way = heappop(not_yet)
        if way == 1:
            ans = ans1
        elif way == 2:
            ans = ans2
        elif way == 3:
            ans = ans3
        else:
            ans = ans4

        if cost == 0 or ans[x][y] < 0:
            ans[x][y] = cost
        
        if already[x][y]:
            continue
        
        already[x][y] = True

        for v in [1, 2, 3, 4]:
            x_next = x
            y_next = y
            if v == 1:
                x_next += 1
            elif v == 2:
                x_next -= 1
            elif v == 4:
                y_next += 1
            else:
                y_next -= 1

            if v == way:
                cost_next = cost + 1
                if cost_next % mod % k == 0:
                    cost_next = (cost_next//mod+1)*mod
            else:
                cost_next = (cost//mod+1)*mod

            heappush(not_yet, (cost_next, x_next, y_next, v))


    ans = [ans1[gx][gy]//mod, ans2[gx][gy]//mod, ans3[gx][gy]//mod, ans4[gx][gy]//mod]

    answer = mod
    for v in ans:
        if v != -1:
            answer = min(answer, v)
    
    if answer == mod:
        answer = -1
    
    print(answer)
    

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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]==inf:
        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]==inf:
            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: Wrong Answer

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] < m + 1: break
                if d[nx][ny] == m + 1: continue
                d[nx][ny] = m + 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: Wrong Answer

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:
        n,x,y =  heapq.heappop(q)
        if d[x][y] <= n: continue
        d[x][y] = n
        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((d[nx][ny],nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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:
        n,x,y =  heapq.heappop(q)
        if d[x][y] <= n: continue
        d[x][y] = n
        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((d[nx][ny],nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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:
        n,x,y =  heapq.heappop(q)
        if d[x][y] <= n: continue
        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((d[nx][ny],nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    pond = [input().replace("\n", "") for _ in range(h)]
    
    dist_N = [[None]*w for _ in range(h)]
    dist_S = [[None]*w for _ in range(h)]
    dist_E = [[None]*w for _ in range(h)]
    dist_W = [[None]*w for _ in range(h)]
    
    already = [[[True]*4 for _ in range(w)] for _ in range(h)]
    
    not_yet = [(1, 0, sx-1, sy-1, "N"), (1, 0, sx-1, sy-1, "E"), (1, 0, sx-1, sy-1, "S"), (1, 0, sx-1, sy-1, "W")]
    heapify(not_yet)
    already[sx-1][sy-1][0] = False
    already[sx-1][sy-1][1] = False
    already[sx-1][sy-1][2] = False
    already[sx-1][sy-1][3] = False
    
    while not_yet:
        a, b, x, y, d = heappop(not_yet)
        if x != sx-1 or y != sy-1:
            if already[x][y][0]:
                already[x][y][0] = False
                not_yet.append((a, k-1, x, y, "N"))
            if already[x][y][1]:
                already[x][y][1] = False
                not_yet.append((a, k-1, x, y, "S"))
            if already[x][y][2]:
                already[x][y][2] = False
                not_yet.append((a, k-1, x, y, "W"))
            if already[x][y][3]:
                already[x][y][3] = False
                not_yet.append((a, k-1, x, y, "E"))
        if d == "N" and dist_N[x][y] == None:
            dist_N[x][y] = (a, b)
            if x > 0 and already[x-1][y][0] and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                already[x-1][y][0] = False
                if b == k-1:
                    not_yet.append((a+1, 0, x-1, y, "N"))
                else:
                    not_yet.append((a, b+1, x-1, y, "N"))
        if d == "W" and dist_W[x][y] == None:
            dist_W[x][y] = (a, b)
            if y > 0 and already[x][y-1][2] and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                already[x][y-1][2] = False
                if b == k-1:
                    not_yet.append((a+1, 0, x, y-1, "W"))
                else:
                    not_yet.append((a, b+1, x, y-1, "W"))
        if d == "S" and dist_S[x][y] == None:
            dist_S[x][y] = (a, b)
            if x < h-1 and already[x+1][y][1] and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                already[x+1][y][1] = False
                if b == k-1:
                    not_yet.append((a+1, 0, x+1, y, "S"))
                else:
                    not_yet.append((a, b+1, x+1, y, "S"))
        if d == "E" and dist_E[x][y] == None:
            dist_E[x][y] = (a, b)
            if y < w-1 and already[x][y+1][3] and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                already[x][y+1][3] = False
                if b == k-1:
                    not_yet.append((a+1, 0, x, y+1, "E"))
                else:
                    not_yet.append((a, b+1, x, y+1, "E"))
        
    gx -= 1
    gy -= 1
    ans = [10**7]
    
    for v in [dist_N[gx][gy], dist_S[gx][gy], dist_E[gx][gy], dist_W[gx][gy]]:
        if v != None:
            ans.append(v[0])
    
    answer = min(ans)
    print(-1 if answer == 10**7 else answer)
    
    print(dist_E)
        
        
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections

H, W, K = [int(x) for x in input().split()]
X1, Y1, X2, Y2 = [int(x) for x in input().split()]
C = [input().strip() for _ in range(H)]

ans = [[float("inf")] * W for j in range(H)]

q = collections.deque()
q.append((X1 - 1, Y1 - 1))

ans[X1 - 1][Y1 - 1] = 0

while q:
    cx, cy = q.popleft()
    cc = ans[cx][cy]

    # right
    for i in range(1, K + 1):
        if cy + i >= W or C[cx][cy + i] == "@":
            break
        if ans[cx][cy + i] <= cc + 2:
            break
        if ans[cx][cy + i] <= cc + 1:
            continue
        ans[cx][cy + i] = cc + 1
        q.append((cx, cy + i))
    # left
    for i in range(1, K + 1):
        if cy - i <= -1 or C[cx][cy - i] == "@":
            break
        if ans[cx][cy - i] <= cc + 2:
            break
        if ans[cx][cy - i] <= cc + 1:
            continue
        ans[cx][cy - i] = cc + 1
        q.append((cx, cy - i))
    # up
    for i in range(1, K + 1):
        if cx - i <= -1 or C[cx - i][cy] == "@":
            break
        if ans[cx - i][cy] <= cc + 2:
            break
        if ans[cx - i][cy] <= cc + 1:
            continue
        ans[cx - i][cy] = cc + 1
        q.append((cx - i, cy))
    # down
    for i in range(1, K + 1):
        if cx + i >= H or C[cx + i][cy] == "@":
            break
        if ans[cx + i][cy] <= cc + 2:
            break
        if ans[cx + i][cy] <= cc + 1:
            continue
        ans[cx + i][cy] = cc + 1
        q.append((cx + i, cy))


if ans[X2 - 1][Y2 - 1] == float("inf"):
    print(-1)
else:
    print(ans[X2 - 1][Y2 - 1])

Submission status: Wrong Answer

Solution code:
import collections

H, W, K = [int(x) for x in input().split()]
X1, Y1, X2, Y2 = [int(x) for x in input().split()]
C = [input().strip() for _ in range(H)]


ans = [[float("inf")] * W for j in range(H)]


q = collections.deque()
q.append((X1 - 1, Y1 - 1))

ans[X1 - 1][Y1 - 1] = 0

while q:
    cx, cy = q.popleft()
    cc = ans[cx][cy]

    # right
    for i in range(1, K + 1):
        if cy + i >= W or C[cx][cy + i] == "@":
            break
        if ans[cx][cy + i] <= cc + 2:
            break
        ans[cx][cy + i] = cc + 1
        q.append((cx, cy + i))
    # left
    for i in range(1, K + 1):
        if cy - i <= -1 or C[cx][cy - i] == "@":
            break
        if ans[cx][cy - i] <= cc + 2:
            break
        ans[cx][cy - i] = cc + 1
        q.append((cx, cy - i))
    # up
    for i in range(1, K + 1):
        if cx - i <= -1 or C[cx - i][cy] == "@":
            break
        if ans[cx - i][cy] <= cc + 2:
            break
        ans[cx - i][cy] = cc + 1
        q.append((cx - i, cy))
    # down
    for i in range(1, K + 1):
        if cx + i >= H or C[cx + i][cy] == "@":
            break
        if ans[cx + i][cy] <= cc + 2:
            break
        ans[cx + i][cy] = cc + 1
        q.append((cx + i, cy))

if ans[X2 - 1][Y2 - 1] == float("inf"):
    print(-1)
else:
    print(ans[X2 - 1][Y2 - 1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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())
    c = [input() for _ in range(H)]

    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    INF = 10**12
    
    for i in range(H):
        for j in range(W):
            if c[i][j] == '@': continue
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W and c[y][x] == '.':
                    adj[W*i+j].append(W*y+x)
    
    queue = deque([W*x1+y1])
    visit = [INF] * (W*H)
    visit[W*x1+y1] = 0
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            # nowからuの方向に'.'が続くかぎり（最大K個）
            count = 0
            direct = u - now
            fromC = now
            toC = u
            while count < K and toC in adj[fromC] and visit[toC] == INF:
                count += 1
                queue.append(toC)
                visit[toC] = min(visit[toC], visit[now] + 1)
                fromC = toC
                toC += direct 

    print(visit[W*x2+y2]) if visit[W*x2+y2] < INF else print(-1)
    # print(visit)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,K = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1
Pond = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp = list(temp)
  Pond.append(temp)
#print(Pond)
Q = deque([])
Q.append((sx,sy))
reach = [[INF]*W for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  nx,ny = Q.popleft()
  step = K
  for i in range(4):
    for fac in range(1,K+1):
      tx = nx + fac*dxdy[i][0]
      ty = ny + fac*dxdy[i][1]
      #print(i,tx,ty)
      if 0>tx or tx>=H or 0>ty or ty>=W or Pond[tx][ty] == "@": #or reach[tx][ty] != INF:
        #print(i,tx,ty,reach[2][0])
        break #範囲外やハスがあった、到達済みの場合には終了
      #print(i,tx,ty)
      if reach[nx][ny] + 1 >= reach[tx][ty]: #もし現時点よりもステップが大きい場合はだめ。
        #同じ場合は向き的に得している場合もあるので残す。
        break
      reach[tx][ty] = reach[nx][ny] + 1
      Q.append((tx,ty))
      if tx == gx and ty == gy:
        print(reach[gx][gy])
        exit()
#print(reach)
#ans = reach[gx][gy]
#if ans == INF:
print(-1)
#else:
#  print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

    # 方針: 隣接リストは普通に持つ
    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    for i in range(H):
        for j in range(W):
            if c[i][j] == '@': continue
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W and c[y][x] == '.':
                    adj[W*i+j].append(W*y+x)

    # print(adj)
    
    queue = deque([W*x1+y1])
    visit = [-1] * (W*H)
    visit[W*x1+y1] = 0
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            # nowからuの方向に'.'が続くかぎり（最大K個）
            count = 0
            direct = u - now
            fromC = now
            toC = u
            while count < K and toC in adj[fromC] and visit[toC] < 0:
                count += 1
                queue.append(toC)
                visit[toC] = visit[now] + 1
                fromC = toC
                toC += direct 

    print(visit[W*x2+y2])

if __name__ == "__main__":
    main()