Problem:


Score : 600 points

Problem Statement

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

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

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

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

Constraints

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

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

5

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

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

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

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

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

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

Sample Input 2

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

Sample Output 2

2

Sample Input 3

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

Sample Output 3

-1



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


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappop, heappush

import numpy as np

from numba import njit


@njit('UniTuple(i8[:],4)(i1[:],i8,i8,i8)')
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


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:
        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: Time Limit Exceeded

Solution code:
from collections import deque

import numpy as np

from numba import njit


@njit('UniTuple(i8[:],4)(i1[:],i8,i8,i8)')
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


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 = deque([(0, s)])
    while q:
        cost, v = q.popleft()
        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
            q.append((nc, u))

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

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

        for u in range(rg[v], v, -1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            q.append((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: Time Limit Exceeded

Solution code:
from collections import deque


def reachable(field, h2, w2, k):
    # 各マスから上下左右にどこまで行けるか
    hw = h2 * w2
    up, dw, lf, rg = [-1] * hw, [-1] * hw, [-1] * hw, [-1] * hw
    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


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 = deque([(0, s)])
    while q:
        cost, v = q.popleft()
        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
            q.append((nc, u))

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

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

        for u in range(rg[v], v, -1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            q.append((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 = ['@' * w2]
for row in field_tmp:
    field.append('@' + row + '@')
field.append('@' * w2)
field = ''.join(field)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Submission status: Time Limit Exceeded

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 = ["@"] + list(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)
        if ncost > dist[x][y]:
            continue
        else:
            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, 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:
                nx = x + nd[0]; ny = y + nd[1]
                if nd == (-dx, -dy):
                    continue
                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: Time Limit Exceeded

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)
        if ncost > dist[x][y]:
            continue
        else:
            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, 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:
                nx = x + nd[0]; ny = y + nd[1]
                if nd == (-dx, -dy):
                    continue
                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: Time Limit Exceeded

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)
        if ncost > dist[x][y]:
            continue
        else:
            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, d, step - 1))
            for nd in delta:
                nx = x + nd[0]; ny = y + nd[1]
                if nd == d:
                    continue
                if field[nx][ny] == "." and dist[nx][ny] >= dist[x][y] + 1:
                    dq.append((nx, ny, nd, k))
        else:
            for nd in delta:
                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: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


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, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if y == gy and x == gx:
            print(d)
            sys.exit()
        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] == INF:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
        if ncost > dist[x][y]:
            continue
        else:
            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: Time Limit Exceeded

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, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if y == gy and x == gx:
            print(d)
            sys.exit()
        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] == INF:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if y == gy and x == gx:
            print(dist[y][x])
            sys.exit()
        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] > d+1:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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)
        if ncost > dist[x][y]:
            continue
        else:
            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: Time Limit Exceeded

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()
        if step < k:
            ncost = dist[x - dx][y - dy]
        else:
            ncost = dist[x - dx][y - dy] + 1
        if ncost > dist[x][y]:
            continue
        else:
            dist[x][y] = ncost
        if step > 1:
            if field[x+dx][y+dy] == ".":
                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] == ".":
                    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] == ".":
                    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: Time Limit Exceeded

Solution code:
import sys
inf=10000000
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp[x][y+j]=d
                now.append([x,y+j])
            if dp[x][y+j]==-1:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp[x][y-j]=d
                now.append([x,y-j])
            if dp[x][y-j]==-1:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp[x+j][y]=d
                now.append([x+j,y])
            if dp[x+j][y]==-1:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp[x-j][y]=d
                now.append([x-j,y])
            if dp[x-j][y]==-1:
                break
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

Submission status: Time Limit Exceeded

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()
        if step < k:
            ncost = dist[x - dx][y - dy]
            if ncost > dist[x][y]:
                continue
            else:
                dist[x][y] = ncost
        else:
            ncost = dist[x - dx][y - dy] + 1
            if ncost > dist[x][y]:
                continue
            else:
                dist[x][y] = ncost
        if step > 1:
            if field[x+dx][y+dy] == ".":
                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] == ".":
                    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] == ".":
                    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]))
if dist[gx][gy] == INF:
    print(-1)
else:
    print(dist[gx][gy])

Submission status: Time Limit Exceeded

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 == i 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)