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:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[-1] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] >= 0: continue
        timeij[d] = t
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] >= 0: continue
            if nt == t:
                q.append((nt, i, j, nd))
            else:
                q.appendleft((nt, i, j, nd))
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] >= 0: continue
        q.append((t + 1, ni, nj, d))
    print((min(time[x2][y2][i] for i in range(4)) + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[-1] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] >= 0: continue
        timeij[d] = t
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] >= 0: continue
            q.appendleft((nt, i, j, nd))
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] >= 0: continue
        q.append((t + 1, ni, nj, d))
    print((min(time[x2][y2][i] for i in range(4)) + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[10**12] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = []
    for i in range(4):
        heappush(q, (0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = heappop(q)
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                heappush(q, (nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            heappush(q, (t + 1, ni, nj, d))
            timeninj[d] = t + 1
    print((min(time[x2][y2][i] for i in range(4)) + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[-1] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = [(0, x1, y1, 0)]
    while q:
        t, i, j, d = heappop(q)
        timeij = time[i][j]
        if timeij[d] != -1 and timeij[d] != d: continue
        timeij[d] = t
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] >= 0: break
            heappush(q, ((t + K - 1) // K * K, i, j, nd))
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        if time[ni][nj][d] >= 0: continue
        heappush(q, (t + 1, ni, nj, d))
    print((min(time[x2][y2][i] for i in range(4)) + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[-1] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = [(0, x1, y1, 0)]
    while q:
        t, i, j, d = heappop(q)
        if time[i][j][d] >= 0: continue
        time[i][j][d] = t
        for nd in range(4):
            if nd == d: continue
            if time[i][j][nd] >= 0: continue
            heappush(q, ((t + K - 1) // K * K, i, j, nd))
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        if time[ni][nj][d] >= 0: continue
        heappush(q, (t + 1, ni, nj, d))
    print((min(time[x2][y2][i] for i in range(4)) + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[-1] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = [(0, x1, y1, 0)]
    while q:
        t, i, j, d = heappop(q)
        if time[i][j][d] >= 0: continue
        time[i][j][d] = t
        for nd in range(4):
            if nd == d: continue
            if time[i][j][nd] >= 0: break
            heappush(q, ((t + K - 1) // K * K, i, j, nd))
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        if time[ni][nj][d] >= 0: continue
        heappush(q, (t + 1, ni, nj, d))
    print((min(time[x2][y2][i] for i in range(4)) + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
from math import ceil
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[-1] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = [(0, x1, y1, 0)]
    while q:
        t, i, j, d = heappop(q)
        if time[i][j][d] >= 0: continue
        time[i][j][d] = t
        for nd in range(4):
            if nd == d: continue
            if time[i][j][nd] >= 0: break
            heappush(q, (ceil(t), i, j, nd))
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        if time[ni][nj][d] >= 0: continue
        heappush(q, (t + (1 / K), ni, nj, d))
    print(ceil(min(time[x2][y2][i] for i in range(4))))

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
from math import ceil
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[-1] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = [(0, x1, y1, 0)]
    while q:
        t, i, j, d = heappop(q)
        if time[i][j][d] >= 0: continue
        time[i][j][d] = t
        for nd in range(4):
            if nd == d: continue
            if time[i][j][nd] >= 0: continue
            heappush(q, (ceil(t), i, j, nd))
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        if time[ni][nj][d] >= 0: continue
        heappush(q, (t + (1 / K), ni, nj, d))
    print(ceil(min(time[x2][y2][i] for i in range(4))))

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Wrong Answer

Solution code:
# pond scater

import heapq
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

pond = [list(input()) for _ in range(H)]

graph = {(i, j): [] for i in range(1, H+1) for j in range(1, W+1)}

for i in range(H):
    right = 1
    for j in range(W):
        if pond[i][j] == "@":
            right = j+2
        else:
            while right+1 <= W and right+1 <= j+1+K and pond[i][right] != "@":
                right += 1
            if j+1 != right:
                graph[(i+1, j+1)].append((1, (i+1, right)))
                graph[(i+1, right)].append((1, (i+1, j+1)))
for i in range(H):
    left = W
    for j in range(W-1, -1, -1):
        if pond[i][j] == "@":
            left = j
        else:
            while left-1 >= 1 and left-1 >= j+1-K and pond[i][left-2] != "@":
                left -= 1
            if j+1 != left:
                graph[(i+1, j+1)].append((1, (i+1, left)))
                graph[(i+1, left)].append((1, (i+1, j+1)))

rev_pond = [[0 for i in range(H)] for j in range(W)]
for i in range(H):
    for j in range(W):
        rev_pond[j][i] = pond[i][j]

for i in range(W):
    right = 1
    for j in range(H):
        if rev_pond[i][j] == "@":
            right = j+2
        else:
            while right+1 <= H and right+1 <= j+1+K and rev_pond[i][right] != "@":
                right += 1
            if j+1 != right:
                graph[(j+1, i+1)].append((1, (right, i+1)))
                graph[(right, i+1)].append((1, (j+1, i+1)))

for i in range(W):
    left = H
    for j in range(H-1, -1, -1):
        if rev_pond[i][j] == "@":
            left = j
        else:
            while left-1 >= 1 and left-1 >= j+1-K and rev_pond[i][left-2] != "@":
                left -= 1
            if j+1 != left:
                graph[(j+1, i+1)].append((1, (left, i+1)))
                graph[(left, i+1)].append((1, (j+1, i+1)))


# graph表示完成

dist = {(i, j): 10**20 for i in range(H+1) for j in range(W+1)}
dist[(x1, y1)] = 0
pq = []
heapq.heapify(pq)

heapq.heappush(pq, (0, (x1, y1)))
while pq:
    x = heapq.heappop(pq)
    node, mini_dis = x[1], x[0]
    if dist[node] < mini_dis:
        continue
    for w, point in graph[node]:
        newlen = dist[node]+w
        if newlen < dist[point]:
            heapq.heappush(pq, (newlen, point))
            dist[point] = newlen
ANS = dist[(x2, y2)]
if ANS <10**20:
    print(ANS)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
from math import ceil
from math import isclose
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [INF if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    heapify(stack)
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        curr, x, y, d = heappop(stack)
        xx = x + DX[d]
        yy = y + DY[d]
        a = curr + 1 / K - EPS
        b = int(ceil(a))
        if c[xx][yy] < a:
            continue
        if (xx, yy) == (x2, y2):
            print(b)
            return
        if c[xx][yy] > a:
            c[xx][yy] = a
            heappush(stack, (b, xx, yy, (d - 1) % 4))
            heappush(stack, (b, xx, yy, (d + 1) % 4))
            heappush(stack, (a, xx, yy, d))
        elif isclose(c[xx][yy], a):
            heappush(stack, (a, xx, yy, d))

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
from math import ceil
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [INF if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    heapify(stack)
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        curr, x, y, d = heappop(stack)
        xx = x + DX[d]
        yy = y + DY[d]
        a = curr + 1 / K - EPS
        b = int(ceil(a))
        if c[xx][yy] < a:
            continue
        if (xx, yy) == (x2, y2):
            print(b)
            return
        if c[xx][yy] > a:
            c[xx][yy] = a
            heappush(stack, (b, xx, yy, (d - 1) % 4))
            heappush(stack, (b, xx, yy, (d + 1) % 4))
            heappush(stack, (a, xx, yy, d))
        elif c[xx][yy] == a:
            heappush(stack, (a, xx, yy, d))

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify, merge
from math import ceil
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [["@"] + [i for i in input()] + ["@"] for i in range(H)]
    c = [["@"] * (W + 2)] + c + [["@"] * (W + 2)]
    dd = [cc[:] for cc in c]

    dist = [[INF] * (W + 2) for i in range(H + 2)]
    dist[x1][y1] = 0

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    invk = 1 / K - EPS
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        new_stack = []
        head = 0
        while head < len(stack):
            curr, x, y, d = stack[head]
            head += 1
            # print(curr, x, y, d)
            xx = x + DX[d]
            yy = y + DY[d]
            if c[xx][yy] == "@":
                continue
            if (xx, yy) == (x2, y2):
                print(int(ceil(curr + invk)))
                # print(*dist, sep="\n")
                return
            a = curr + invk
            b = int(ceil(a))
            dd[xx][yy] = "@"
            new_stack.append((b, xx, yy, (d - 1) % 4))
            new_stack.append((b, xx, yy, (d + 1) % 4))
            stack.append((a, xx, yy, d))
        stack = new_stack
        dd, c = c, dd
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
from math import ceil
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    c = [[c for c in input()] for i in range(H)]
    dist = [[INF] * W for i in range(H)]
    dist[x1][y1] = 0

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    while stack:
        curr, x, y, d = heappop(stack)
        # print(curr, x, y, d)
        if d == 0:
            dx, dy = 1, 0
        elif d == 1:
            dx, dy = 0, 1
        elif d == 2:
            dx, dy = -1, 0
        else:
            dx, dy = 0, -1
        xx = x + dx
        yy = y + dy
        if not(0 <= xx < H):
            continue
        if not(0 <= yy < W):
            continue
        if c[xx][yy] == "@":
            continue
        if (xx, yy) == (x2, y2):
            print(int(ceil(curr + 1 / K)))
            # print(*dist, sep="\n")
            return
        if dist[xx][yy] >= curr + 1 / K:
            dist[xx][yy] = curr + 1 / K
            heappush(stack, (int(ceil(curr + 1 / K)), xx, yy, (d - 1) % 4))
            heappush(stack, (int(ceil(curr + 1 / K)), xx, yy, (d + 1) % 4))
            heappush(stack, (curr + 1 / K, xx, yy, d))
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
from math import ceil
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    c = [[c for c in input()] for i in range(H)]
    dist = [[INF] * W for i in range(H)]
    dist[x1][y1] = 0
    # table = [[-1] * H for _ in range(W)]
    # table[x1][y1] = 0
    # print(c)

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    while stack:
        curr, x, y, d = heappop(stack)
        # print(curr, x, y, d)
        if d == 0:
            dx, dy = 1, 0
        elif d == 1:
            dx, dy = 0, 1
        elif d == 2:
            dx, dy = -1, 0
        else:
            dx, dy = 0, -1
        xx = x + dx
        yy = y + dy
        if not(0 <= xx < H):
            continue
        if not(0 <= yy < W):
            continue
        if c[xx][yy] == "@":
            continue
        if (xx, yy) == (x2, y2):
            print(int(ceil(curr + 1 / K)))
            # print(*dist, sep="\n")
            return
        if dist[xx][yy] > int(ceil(curr + 1 / K)):
            dist[xx][yy] = int(ceil(curr + 1 / K))
            heappush(stack, (int(ceil(curr + 1 / K)), xx, yy, (d - 1) % 4))
            heappush(stack, (int(ceil(curr + 1 / K)), xx, yy, (d + 1) % 4))
            heappush(stack, (curr + 1 / K, xx, yy, d))
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    c = [[c for c in input()] for i in range(H)]
    seen = [[0] * W for i in range(H)]
    seen[x1][y1] = 1
    # table = [[-1] * H for _ in range(W)]
    # table[x1][y1] = 0
    # print(c)

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    while stack:
        curr, x, y, d = heappop(stack)
        # print(x, y, d, curr)
        if d == 0:
            flag = True
            for yy in range(y + 1, y + K + 1):
                if W <= yy:
                    flag = False
                    break
                # print(x, y, yy)
                if c[x][yy] == "@":
                    flag = False
                    break
                if seen[x][yy] == 1:
                    continue
                if (x, yy) == (x2, y2):
                    print(curr + 1)
                    return
                # table[x][yy] = curr + 1
                heappush(stack, (curr + 1, x, yy, 2))
                heappush(stack, (curr + 1, x, yy, 3))
                seen[x][yy] = 1
            if flag:
                heappush(stack, (curr + 1, x, yy, 0))
        elif d == 1:
            flag = True
            for yy in range(y - 1, y - K - 1, -1):
                if 0 > yy:
                    flag = False
                    break
                if c[x][yy] == "@":
                    flag = False
                    break
                if seen[x][yy] == 1:
                    continue
                if (x, yy) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, x, yy, 2))
                heappush(stack, (curr + 1, x, yy, 3))
                seen[x][yy] = 1
            if flag:
                heappush(stack, (curr + 1, x, yy, 0))
        elif d == 2:
            flag = True
            for xx in range(x - 1, x - K - 1, -1):
                if 0 > xx:
                    flag = False
                    break
                if c[xx][y] == "@":
                    flag = False
                    break
                if seen[xx][y] == 1:
                    continue
                if (xx, y) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, xx, y, 0))
                heappush(stack, (curr + 1, xx, y, 1))
                seen[xx][y] = 1
            if flag:
                heappush(stack, (curr + 1, xx, y, 2))
        elif d == 3:
            flag = True
            for xx in range(x + 1, x + K + 1):
                if xx >= H:
                    flag = False
                    break
                if c[xx][y] == "@":
                    flag = False
                    break
                if seen[xx][y] == 1:
                    continue
                if (xx, y) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, xx, y, 0))
                heappush(stack, (curr + 1, xx, y, 1))
                seen[xx][y] = 1
            if flag:
                heappush(stack, (curr + 1, xx, y, 3))
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    c = [[c for c in input()] for i in range(H)]
    # table = [[-1] * H for _ in range(W)]
    # table[x1][y1] = 0
    # print(c)

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    while stack:
        curr, x, y, d = heappop(stack)
        # print(x, y, d, curr)
        if d == 0:
            flag = True
            for yy in range(y + 1, y + K + 1):
                if W <= yy:
                    flag = False
                    break
                # print(x, y, yy)
                if c[x][yy] == "@":
                    flag = False
                    break
                if (x, yy) == (x2, y2):
                    print(curr + 1)
                    return
                # table[x][yy] = curr + 1
                heappush(stack, (curr + 1, x, yy, 2))
                heappush(stack, (curr + 1, x, yy, 3))
                c[x][yy] = "@"
            if flag:
                heappush(stack, (curr + 1, x, yy, 0))
        elif d == 1:
            flag = True
            for yy in range(y - 1, y - K - 1, -1):
                if 0 > yy:
                    flag = False
                    break
                if c[x][yy] == "@":
                    flag = False
                    break
                if (x, yy) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, x, yy, 2))
                heappush(stack, (curr + 1, x, yy, 3))
                c[x][yy] = "@"
            if flag:
                heappush(stack, (curr + 1, x, yy, 0))
        elif d == 2:
            flag = True
            for xx in range(x - 1, x - K - 1, -1):
                if 0 > xx:
                    flag = False
                    break
                if c[xx][y] == "@":
                    flag = False
                    break
                if (xx, y) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, xx, y, 0))
                heappush(stack, (curr + 1, xx, y, 1))
                c[xx][y] = "@"
            if flag:
                heappush(stack, (curr + 1, xx, y, 2))
        elif d == 3:
            flag = True
            for xx in range(x + 1, x + K + 1):
                if xx >= H:
                    flag = False
                    break
                if c[xx][y] == "@":
                    flag = False
                    break
                if (xx, y) == (x2, y2):
                    print(curr + 1)
                    return
                heappush(stack, (curr + 1, xx, y, 0))
                heappush(stack, (curr + 1, xx, y, 1))
                c[xx][y] = "@"
            if flag:
                heappush(stack, (curr + 1, xx, y, 3))
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from queue import Queue


def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(lambda z: int(z) - 1, input().split())
    c = [list(input().replace('\n', '')) for _ in range(h)]
    c[sx][sy] = 0
    q = Queue()
    q.put((sx, sy))
    while not q.empty():
        x, y = q.get()
        d = c[x][y]
        # 南へ移動
        for i in range(1, k + 1):
            if x + i >= h:
                break
            if c[x + i][y] == '@':
                break
            elif isinstance(c[x + i][y], int) and c[x + i][y] <= d + 1:
                break
            else:
                c[x + i][y] = d + 1
                q.put((x + i, y))
        # 北へ移動
        for i in range(1, k + 1):
            if x - i < 0:
                break
            if c[x - i][y] == '@':
                break
            elif isinstance(c[x - i][y], int) and c[x - i][y] <= d + 1:
                break
            else:
                c[x - i][y] = d + 1
                q.put((x - i, y))
        # 東へ移動
        for i in range(1, k + 1):
            if y + i >= w:
                break
            if c[x][y + i] == '@':
                break
            elif isinstance(c[x][y + i], int) and c[x][y + i] <= d + 1:
                break
            else:
                c[x][y + i] = d + 1
                q.put((x, y + i))
        # 西へ移動
        for i in range(1, k + 1):
            if y - i < 0:
                break
            if c[x][y - i] == '@':
                break
            elif isinstance(c[x][y - i], int) and c[x][y - i] <= d + 1:
                break
            else:
                c[x][y - i] = d + 1
                q.put((x, y - i))
    print(-1 if c[gx][gy] == '.' else c[gx][gy])


if __name__ == '__main__':
    main()