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:
from collections import deque


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

INF = float('inf')
path = [[INF] * W for _ in range(H)]
# pathD = [[INF] * W for _ in range(H)]
path[x1][y1] = 0
# pathD[x1][y1] = 0

q = deque()
q.append((x1, y1, 0, 0, 0))
D = ((0, 1), (1, 0), (0, -1), (-1, 0))
q_append = q.append
q_appendleft = q.appendleft
while q:
    x, y, d, k, s = q.popleft()
    if k == 0:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] >= s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, nd, K - 1, s + 1))
    else:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] > ns:
                path[nx][ny] = ns
                nk = k - 1 if d == nd else K - 1
                appendQ = q_appendleft if d == nd else q_append
                appendQ((nx, ny, nd, nk, ns))

ans = -1 if path[x2][y2] == INF else path[x2][y2]
print(ans)

Submission status: Wrong Answer

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())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[INF] * W for _ in range(H)]
# pathD = [[INF] * W for _ in range(H)]
path[x1][y1] = 0
# pathD[x1][y1] = 0

q = deque()
q.append((x1, y1, 0, 0, 0))
D = ((0, 1), (1, 0), (0, -1), (-1, 0))
q_append = q.append
q_appendleft = q.appendleft
while q:
    x, y, d, k, s = q.popleft()
    if k == 0:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, nd, K - 1, s + 1))
    else:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] >= ns:
                path[nx][ny] = ns
                nk = k - 1 if d == nd else K - 1
                appendQ = q_appendleft if d == nd else q_append
                appendQ((nx, ny, nd, nk, ns))

ans = -1 if path[x2][y2] == INF else path[x2][y2]
print(ans)

Submission status: Wrong Answer

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())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[INF] * W for _ in range(H)]
# pathD = [[INF] * W for _ in range(H)]
path[x1][y1] = 0
# pathD[x1][y1] = 0

q = deque()
q.append((x1, y1, 0, 0, 0))
D = ((0, 1), (1, 0), (0, -1), (-1, 0))
q_append = q.append
q_appendleft = q.appendleft
while q:
    x, y, d, k, s = q.popleft()
    if k == 0:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, nd, K - 1, s + 1))
    else:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] > ns:
                path[nx][ny] = ns
                nk = k - 1 if d == nd else K - 1
                appendQ = q_appendleft if d == nd else q_append
                appendQ((nx, ny, nd, nk, ns))

ans = -1 if path[x2][y2] == INF else path[x2][y2]
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

import numpy as np

from numba import njit


@njit('UniTuple(i8[:],4)(i1[:],i8,i8,i8)', cache=True)
def reachable(field, h2, w2, k):
    # 各マスから上下左右にどこまで行けるか
    hw = h2 * w2
    up = np.full(hw, -1, dtype=np.int64)
    dw = np.full(hw, -1, dtype=np.int64)
    lf = np.full(hw, -1, dtype=np.int64)
    rg = np.full(hw, -1, dtype=np.int64)
    lf_tmp = -1
    for i in range(w2, hw - w2):
        if field[i]:
            if lf_tmp == -1:
                lf_tmp = i
            lf[i] = max(lf_tmp, i - k)
        else:
            lf_tmp = -1
    rg_tmp = -1
    for i in range(hw - w2, w2 - 1, -1):
        if field[i]:
            if rg_tmp == -1:
                rg_tmp = i
            rg[i] = min(rg_tmp, i + k)
        else:
            rg_tmp = -1
    wk = w2 * k
    for j in range(1, w2):
        up_tmp = -1
        for i in range(j, hw, w2):
            if field[i]:
                if up_tmp == -1:
                    up_tmp = i
                up[i] = max(up_tmp, i - wk)
            else:
                up_tmp = -1
        dw_tmp = 0
        for i in range(hw - w2 + j, w2 - 1, -w2):
            if field[i]:
                if dw_tmp == -1:
                    dw_tmp = i
                dw[i] = min(dw_tmp, i + wk)
            else:
                dw_tmp = -1
    return up, dw, lf, rg


@njit('i8(i8,i8,i8,i1[:],i8,i8,i8,i8)', cache=True)
def solve(h2, w2, k, field, x1, y1, x2, y2):
    s = x1 * w2 + y1
    t = x2 * w2 + y2
    up, dw, lf, rg = reachable(field, h2, w2, k)

    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0

    q = [(0, s)]
    while q:
        print(q)
        cost, v = heappop(q)
        if v == t:
            return cost
        nc = cost + 1

        for u in range(up[v], v, w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            heappush(q, (nc, u))

        for u in range(dw[v], v, -w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            heappush(q, (nc, u))

        for u in range(lf[v], v, 1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            heappush(q, (nc, u))

        for u in range(rg[v], v, -1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            heappush(q, (nc, u))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = [0] * w2
for row in field_tmp:
    field.append(0)
    field.extend(map('@.'.index, row))
    field.append(0)
field.extend([0] * w2)
field = np.array(field, dtype=np.int8)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque
INF = 10**18

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

field = []
dist = []
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))
for _ in range(h):
    line = "@" + input().rstrip() + "@"
    field.append(line)
    dist.append([-1] + [INF] * (w) + [-1])
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))

# for line in field:
#     print(line)
dist[sx][sy] = 0

delta = ((0, 1), (0, -1), (-1, 0), (1, 0))

def bfs(x, y):
    dq = deque()
    dist[x][y] = 0
    for dx, dy in delta:
        if field[x+dx][y+dy] == ".":
            dq.append((x+dx, y+dy, (dx, dy), k))
    while dq:
        x, y, (dx, dy), step = dq.popleft()
        ncost = dist[x - dx][y - dy] + 1 - (step < k)
        dist[x][y] = ncost
        if step > 1:
            if field[x+dx][y+dy] == "." and dist[x+dx][y+dy] >= dist[x][y]:
                dq.appendleft((x + dx, y + dy, (dx, dy), step - 1))
            for nd in delta:
                ndx = nd[0]; ndy = nd[1]
                if nd == (dx, dy) or nd == (-dx, -dy):
                    continue
                if field[x+ndx][y+ndy] == "." and dist[x+ndx][y+ndy] >= dist[x][y] + 1:
                    dq.append((x + ndx, y + ndy, (ndx, ndy), k))
        else:
            for nd in delta:
                if nd == (-dx, -dy):
                    continue
                ndx = nd[0]; ndy = nd[1]
                if field[x+ndx][y+ndy] == "." and dist[x+ndx][y+ndy] >= dist[x][y] + 1:
                    dq.append((x + ndx, y + ndy, (ndx, ndy), k))

bfs(sx, sy)
# for line in dist:
#     print(" ".join([str(item) for item in line]))
if dist[gx][gy] == INF:
    print(-1)
else:
    print(dist[gx][gy])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque
INF = 10**18

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

field = []
dist = []
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))
for _ in range(h):
    line = "@" + input().rstrip() + "@"
    field.append(line)
    dist.append([-1] + [INF] * (w) + [-1])
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))

# for line in field:
#     print(line)
dist[sx][sy] = 0

delta = ((0, 1), (0, -1), (-1, 0), (1, 0))

def bfs(x, y):
    dq = deque()
    dist[x][y] = 0
    for dx, dy in delta:
        if field[x+dx][y+dy] == ".":
            dq.append((x+dx, y+dy, (dx, dy), k))
    while dq:
        x, y, (dx, dy), step = dq.popleft()
        ncost = dist[x - dx][y - dy] + 1 - (step < k)
        dist[x][y] = ncost
        if step > 1:
            if field[x+dx][y+dy] == "." and dist[x+dx][y+dy] >= dist[x][y]:
                dq.appendleft((x + dx, y + dy, (dx, dy), step - 1))
            for nd in delta:
                nx = x + nd[0]; ny = y + nd[1]
                if nd == (dx, dy) or nd == (-dx, -dy):
                    continue
                if field[nx][ny] == "." and dist[nx][ny] >= dist[x][y] + 1:
                    dq.append((nx, ny, nd, k))
        else:
            for nd in delta:
                if nd == (-dx, -dy):
                    continue
                nx = x + nd[0]; ny = y + nd[1]
                if field[nx][ny] == "." and dist[nx][ny] >= dist[x][y] + 1:
                    dq.append((nx, ny, nd, k))

bfs(sx, sy)
# for line in dist:
#     print(" ".join([str(item) for item in line]))
if dist[gx][gy] == INF:
    print(-1)
else:
    print(dist[gx][gy])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque
INF = 10**18

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

field = []
dist = []
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))
for _ in range(h):
    line = "@" + input().rstrip() + "@"
    field.append(line)
    dist.append([-1] + [INF] * (w) + [-1])
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))

# for line in field:
#     print(line)
dist[sx][sy] = 0

delta = ((0, 1), (0, -1), (-1, 0), (1, 0))

def bfs(x, y):
    dq = deque()
    dist[x][y] = 0
    for dx, dy in delta:
        if field[x+dx][y+dy] == ".":
            dq.append((x+dx, y+dy, (dx, dy), k))
    while dq:
        x, y, d, step = dq.popleft()
        dx = d[0]; dy = d[1]
        ncost = dist[x - dx][y - dy] + 1 - (step < k)
        dist[x][y] = ncost
        if step > 1:
            nx = x + dx; ny = y + dy
            if field[nx][ny] == "." and dist[nx][ny] >= dist[x][y]:
                dq.appendleft((nx, ny, d, step - 1))
            for nd in delta:
                nx = x + nd[0]; ny = y + nd[1]
                if nd == d or nd == (-dx, -dy):
                    continue
                if field[nx][ny] == "." and dist[nx][ny] >= dist[x][y] + 1:
                    dq.append((nx, ny, nd, k))
        else:
            for nd in delta:
                if nd == (-dx, -dy):
                    continue
                nx = x + nd[0]; ny = y + nd[1]
                if field[nx][ny] == "." and dist[nx][ny] >= dist[x][y] + 1:
                    dq.append((nx, ny, nd, k))

bfs(sx, sy)
# for line in dist:
#     print(" ".join([str(item) for item in line]))
if dist[gx][gy] == INF:
    print(-1)
else:
    print(dist[gx][gy])

Submission status: Wrong Answer

Solution code:
#!python3

from heapq import heappop, heappush

LI = lambda: list(map(int, input().split()))

# input
H, W, K = LI()
x1, y1, x2, y2 = LI()
C = [input() for _ in range(H)]

INF = 10 ** 10
w = [[[(INF, 0)] * 4 for _ in range(W)] for _ in range(H)]


def forward(d, x, y):
    if d == 0:
        x -= 1
    elif d == 1:
        x += 1
    elif d == 2:
        y -= 1
    else:
        y += 1
    return x, y


def main():
    hq = []
    for i in range(4):
        w[x1 - 1][y1 - 1][i] = (1, -K)
        hq.append((1, -K, x1 - 1, y1 - 1, i))
    while hq:
        # cost, k, x, y, direction
        c, k, x, y, d = heappop(hq)
        if w[x][y][d] < (c, k):
            continue
        x_, y_ = forward(d, x ,y)
        if 0 <= x_ < H and 0 <= y_ < W:
            if C[x_][y_] == ".":
                if k < 0:
                    if w[x_][y_][d] > (c, k + 1):
                        w[x_][y_][d] = (c, k + 1)
                        heappush(hq, (c, k + 1, x_, y_, d))
                else:
                    if w[x_][y_][d] > (c + 1, K - 1):
                        w[x_][y_][d] = (c + 1, K - 1)
                        heappush(hq, (c + 1, K - 1, x_, y_, d))
        for i in range(4):
            if i == d:
                continue
            if w[x][y][i] > (c + 1, -K):
                w[x][y][i] = (c + 1, -K)
                t = (c + 1, -K, x, y, i)
                heappush(hq, t)

    ans = min(w[x2 - 1][y2 - 1])[0]
    ans = -1 if ans == INF else ans
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    lake = [['@' for _ in range(W+2)]]

    for _ in range(H):
        c = ['@'] + list(readline().decode('utf-8').strip()) + ['@']
        lake.append(c)
    lake.append(['@' for _ in range(W+2)])

    dist = [[INF] * (W+2) for _ in range(H+2)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    Q = deque()
    Q.append((sy, sx))
    dist[sy][sx] = 0
    while Q:
        y,x = Q.popleft()
        if y == gy and x == gx:
            break
        for i in range(4):
            for k in range(1,K+1):
                n_y = y + dy[i] * k
                n_x = x + dx[i] * k

                if lake[n_y][n_x] == '.':
                    if dist[n_y][n_x] > dist[y][x]+1:
                        dist[n_y][n_x] = dist[y][x] + 1
                        Q.append((n_y,n_x))
                    else:
                        break

                else:
                    break

    if dist[gy][gx] == INF:
        print('-1')
    else:
        print(dist[gy][gx])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, w, K = na()
x1, y1, x2, y2 = na()
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1

bd = [ns() for _ in range(h)]

q = []
ds = [9999999999999999] * (h*w*4)

for i in range(4):
    ds[(x1*w+y1)*4+i] = 0
    heappush(q, ds[(x1*w+y1)*4+i]<<60|x1<<40|y1<<20|i)

dr = (1, 0, -1, 0)
dc = (0, 1, 0, -1)
while len(q) > 0:
    cur = heappop(q)
    d = cur>>60
    r = cur>>40&(1<<20)-1
    c = cur>>20&(1<<20)-1
    di = cur&(1<<20)-1
    # d, r, c, di = heappop(q)
    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if 0 <= nr < h and 0 <= nc < w and bd[nr][nc] != "@":
            nd = d + 1 if di == 1 else (d + K-1) // K * K + 1
            nex = (nr*w+nc)*4+i
            if nd < ds[nex]:
                ds[nex] = nd
                heappush(q, nd<<60|nr<<40|nc<<20|i)

ans = min([ds[(x2*w+y2)*4+i] for i in range(4)])
if ans < 999999999999:
    print((ans+K-1)//K)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    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)]

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

    v = set()
    v.add((X1 - 1, Y1 - 1))

    while q:
        c = q.popleft()
        x = c[0]
        y = c[1]
        d = c[2]

        if y == Y2 - 1 and x == X2 - 1:
            print(c[2])
            return

        e, w, n, s = True, True, True, True
        for k in range(1, K + 1):
            if not e and not w and not n and not s:
                break
            if e:
                if y + k >= W or C[x][y + k] == "@":
                    e = False
                else:
                    if (x, y + k) not in v:
                        v.add((x, y + k))
                        q.append((x, y + k, d + 1))
                    else:
                        e = False
            if w:
                if y - k < 0 or C[x][y - k] == "@":
                    w = False
                else:
                    if (x, y - k) not in v:
                        v.add((x, y - k))
                        q.append((x, y - k, d + 1))
                    else:
                        w = False

            if n:
                if x - k < 0 or C[x - k][y] == "@":
                    n = False
                else:
                    if (x - k, y) not in v:
                        v.add((x - k, y))
                        q.append((x - k, y, d + 1))
                    else:
                        n = False

            if s:
                if x + k >= H or C[x + k][y] == "@":
                    s = False
                else:
                    if (x + k, y) not in v:
                        v.add((x + k, y))
                        q.append((x + k, y, d + 1))
                    else:
                        s = False

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, XY1XY2, C):
    q = deque()
    s = (XY1XY2[0]-1)*W + XY1XY2[1]-1
    go = (XY1XY2[2]-1)*W + XY1XY2[3]-1
    q.append(s)
    d = {s: 0}

    rem = set()
    for i in range(H):
        for j in range(W):
            if C[i][j] == '.':
                rem.add(i*W+j)
    rem.remove(s)
    while q and rem:
        u = q.popleft()
        i = u // W
        j = u % W
        e = list()
        for k in range(1, K+1):
            if i - k >= 0 and C[i-k][j] != '@':
                n = (i-k)*W + j
                if n not in d:
                    e.append(n)
                else:
                    break
            else:
                break
        for k in range(1, K+1):
            if i + k < H and C[i+k][j] != '@':
                n = (i+k)*W + j
                if n not in d:
                    e.append(n)
                else:
                    break
            else:
                break
        for k in range(1, K+1):
            if j - k >= 0 and C[i][j-k] != '@':
                n = i*W + j-k
                if n not in d:
                    e.append(n)
                else:
                    break
            else:
                break
        for k in range(1, K+1):
            if j + k < W and C[i][j+k] != '@':
                n = i*W + j+k
                if n not in d:
                    e.append(n)
                else:
                    break
            else:
                break
        for v in e:
            q.append(v)
            d[v] = d[u] + 1
            rem.remove(v)
            if v == go:
                return d[v]

    return -1


def main():
    H, W, K = read_int_n()
    XY1XY2 = read_int_n()

    C = [read_str() for _ in range(H)]
    print(slv(H, W, K, XY1XY2, C))

    # H = 1000
    # W = 1000
    # K = 1000
    # XY1XY2 = [1, 1, H, W]
    # C = [['.'] * W for _ in range(H)]
    # for i in range(1, H, 2):
    #     if ((i + 1) // 2) % 2 == 1:
    #         for j in range(W-1):
    #             C[i][j] = '@'
    #     else:
    #         for j in range(1, W):
    #             C[i][j] = '@'

    # # for r in C:
    # #     print(r)
    # print(slv(H, W, K, XY1XY2, C))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

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

field = []
dist = []
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))
for _ in range(h):
    line = "@" + input().rstrip() + "@"
    field.append(line)
    dist.append([-1] * (w + 2))
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))

# for line in field:
#     print(line)
dist[sx][sy] = 0

delta = [(0, 1), (0, -1), (-1, 0), (1, 0)]

def bfs(x, y):
    dq = deque()
    dist[x][y] = 0
    for dx, dy in delta:
        if field[x+dx][y+dy] == ".":
            dq.append((x+dx, y+dy, (dx, dy), k))
    while dq:
        x, y, (dx, dy), step = dq.popleft()
        if dist[x][y] != -1:
            continue
        else:
            if step < k:
                dist[x][y] = dist[x - dx][y - dy]
            else:
                dist[x][y] = dist[x - dx][y - dy] + 1
        if step > 1:
            if field[x+dx][y+dy] == "." and dist[x+dx][y+dy] == -1:
                dq.appendleft((x + dx, y + dy, (dx, dy), step - 1))
                # dist[x+dx][y+dy] = dist[x][y]
            for nd in delta:
                ndx = nd[0]; ndy = nd[1]
                if nd == (dx, dy):
                    continue
                if field[x+ndx][y+ndy] == "." and dist[x+ndx][y+ndy] == -1:
                    dq.append((x + ndx, y + ndy, (ndx, ndy), k))
                    # dist[x+ndx][y+ndy] = dist[x][y] + 1
        else:
            for nd in delta:
                ndx = nd[0]; ndy = nd[1]
                if field[x+ndx][y+ndy] == "." and dist[x+ndx][y+ndy] == -1:
                    dq.append((x + ndx, y + ndy, (ndx, ndy), k))
                    # dist[x+ndx][y+ndy] = dist[x][y] + 1

bfs(sx, sy)
# for line in dist:
#     print(" ".join([str(item) for item in line]))
print(dist[gx][gy])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

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

field = []
dist = []
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))
for _ in range(h):
    line = "@" + input().rstrip() + "@"
    field.append(line)
    dist.append([-1] * (w + 2))
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))

# for line in field:
#     print(line)
dist[sx][sy] = 0

delta = [(0, 1), (0, -1), (-1, 0), (1, 0)]

def bfs(x, y):
    dq = deque()
    dist[x][y] = 1
    for dx, dy in delta:
        if field[x+dx][y+dy] == ".":
            dq.append((x+dx, y+dy, (dx, dy), k-1))
    while dq:
        x, y, (dx, dy), step = dq.popleft()
        if dist[x][y] != -1:
            continue
        else:
            if step < k:
                dist[x][y] = dist[x - dx][y - dy]
            else:
                dist[x][y] = dist[x - dx][y - dy] + 1
        if step > 1:
            if field[x+dx][y+dy] == "." and dist[x+dx][y+dy] == -1:
                dq.appendleft((x + dx, y + dy, (dx, dy), step - 1))
                # dist[x+dx][y+dy] = dist[x][y]
            for nd in delta:
                ndx = nd[0]; ndy = nd[1]
                if nd == (dx, dy):
                    continue
                if field[x+ndx][y+ndy] == "." and dist[x+ndx][y+ndy] == -1:
                    dq.append((x + ndx, y + ndy, (ndx, ndy), k))
                    # dist[x+ndx][y+ndy] = dist[x][y] + 1
        else:
            for nd in delta:
                ndx = nd[0]; ndy = nd[1]
                if field[x+ndx][y+ndy] == "." and dist[x+ndx][y+ndy] == -1:
                    dq.append((x + ndx, y + ndy, (ndx, ndy), k))
                    # dist[x+ndx][y+ndy] = dist[x][y] + 1

bfs(sx, sy)
print(dist[gx][gy])

Submission status: Wrong Answer

Solution code:
from math import inf
from collections import deque
import sys

H,W,K=map(int,input().split())
x,y,u,v=map(int,input().split())
M=["N","E","W","S"]
C=[[]]
D={}
E={}

for a in range(H):
    P=input()
    C.append("*"+P)
    for b in range(W):
        if P[b]==".":
            for d in M:
                D[((a+1,b+1),d)]=inf
        

for d in M:
    D[((x,y),d)]=0

L={"N":(1,0),"E":(0,1),"S":(-1,0),"W":(0,-1)}
while D:
    ((p,q),d)=min(D,key=lambda x:D[x])
    g=D[((p,q),d)]
    E[((p,q),d)]=g
    del D[((p,q),d)]

    (a,b)=L[d]
    for m in range(1,K+1):
        X=p+a*m
        Y=q+b*m
        if (1<=X<=H) and (1<=Y<=W):
            if C[X][Y]==".":
                if ((X,Y),d) in D:
                    D[((X,Y),d)]=min(D[((X,Y),d)],g+m)
            else:
                break
        else:
            break
        

    for a in M:
        if ((p,q),a) in D:
            if D[((p,q),a)]<inf:
                D[((p,q),a)]=int((g+K-1)//K)*K

if E[((u,v),"N")]==inf:
    print(-1)
else:
    print(E[((u,v),"N")]//K)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def BFS(H, W, L, start, K):
	dist = [[INF for i in range(W + 2)] for j in range(H + 2)]
	prev = [[None for i in range(W + 2)] for j in range(H + 2)]
	sy, sx, h, w = start; dist[sy][sx] = 0
	Q = deque(); Q.append([sy, sx, h, w])
	while Q:
		y, x, h, w = Q.popleft()
		if L[y - 1][x] == ".":
			if h == 0:
				if dist[y - 1][x] >= dist[y][x] + 1:
					dist[y - 1][x] = dist[y][x] + 1
					prev[y - 1][x] = 0
					Q.append([y - 1, x, K - 1, 0])
			else:
				if dist[y - 1][x] > dist[y][x]:
					dist[y - 1][x] = dist[y][x]
					prev[y - 1][x] = 0
					Q.appendleft([y - 1, x, h - 1, 0])
				elif dist[y - 1][x] == dist[y][x] and prev[y - 1][x] == 1:
					Q.appendleft([y - 1, x, h - 1, 0])

		if L[y + 1][x] == ".":
			if h == 0:
				if dist[y + 1][x] >= dist[y][x] + 1:
					dist[y + 1][x] = dist[y][x] + 1
					prev[y + 1][x] = 0
					Q.append([y + 1, x, K - 1, 0])
			else:
				if dist[y + 1][x] > dist[y][x]:
					dist[y + 1][x] = dist[y][x]
					prev[y + 1][x] = 0
					Q.appendleft([y + 1, x, h - 1, 0])
				elif dist[y + 1][x] == dist[y][x] and prev[y + 1][x] == 1:
					Q.appendleft([y + 1, x, h - 1, 0])

		if L[y][x - 1] == ".":
			if w == 0:
				if dist[y][x - 1] >= dist[y][x] + 1:
					dist[y][x - 1] = dist[y][x] + 1
					prev[y][x - 1] = 1
					Q.append([y, x - 1, 0, K - 1])
			else:
				if dist[y][x - 1] > dist[y][x]:
					dist[y][x - 1] = dist[y][x]
					prev[y][x - 1] = 1
					Q.appendleft([y, x - 1, 0, w - 1])
				elif dist[y][x - 1] == dist[y][x] and prev[y][x - 1] == 0:
					Q.appendleft([y, x - 1, 0, w - 1])

		if L[y][x + 1] == ".":
			if w == 0:
				if dist[y][x + 1] >= dist[y][x] + 1:
					dist[y][x + 1] = dist[y][x] + 1
					prev[y][x + 1] = 1
					Q.append([y, x + 1, 0, K - 1])
			else:
				if dist[y][x + 1] > dist[y][x]:
					dist[y][x + 1] = dist[y][x]
					prev[y][x + 1] = 1
					Q.appendleft([y, x + 1, 0, w - 1])
				elif dist[y][x + 1] == dist[y][x] and prev[y][x + 1] == 0:
					Q.appendleft([y, x + 1, 0, w - 1])

	return dist

#処理内容
def main():
	H, W, K = getlist()
	y1, x1, y2, x2 = getlist()
	L = []
	L.append(["@"] * (W + 2))
	for i in range(H):
		l = list(input())
		L.append(["@"] + l + ["@"])
	L.append(["@"] * (W + 2))

	#node = [y, x, h, w]
	start = [y1, x1, 0, 0]
	BF = BFS(H, W, L, start, K)
	ans = BF[y2][x2]

	# for i in range(H + 2):
	# 	print(BF[i])

	if ans == INF:
		print(-1)
	else:
		print(ans)

if __name__ == '__main__':
	main()