Problem:


Score : 600 points

Problem Statement

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

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

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

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

Constraints

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

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

5

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

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

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

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

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

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

Sample Input 2

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

Sample Output 2

2

Sample Input 3

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

Sample Output 3

-1



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


Sample output:
5

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

h, w, k = LI()
sy, sx, gy, gx = LI()
cost = [[INF] * w for _ in range(h)]
cost[sy - 1][sx - 1] = 0
grid = SR(h)
q = deque([(sy - 1, sx - 1)])
while q:
    cy, cx = q.popleft()
    for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        for l in range(1, k + 1):
            ny, nx = cy + i * l, cx + j * l
            if 0 <= nx < w and 0 <= ny < h and grid[ny][nx] == "." and cost[ny][nx] >= cost[cy][cx] + 1:
                if cost[ny][nx] == INF:
                    q.append((ny, nx))
                    cost[ny][nx] = cost[cy][cx] + 1
            else:
                break


print(cost[gy - 1][gx - 1] if cost[gy - 1][gx - 1] != INF else -1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

h, w, k = LI()
sy, sx, gy, gx = LI()
cost = [[INF] * w for _ in range(h)]
cost[sy - 1][sx - 1] = 0
grid = SR(h)
q = deque([(sy - 1, sx - 1)])
while q:
    cy, cx = q.popleft()
    for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        for l in range(1, k + 1):
            ny, nx = cy + i * l, cx + j * l
            if 0 <= nx < w and 0 <= ny < h and grid[ny][nx] == "." and cost[ny][nx] >= cost[cy][cx] + 1:
                if cost[ny][nx] == INF:
                    q.append((ny, nx))
                cost[ny][nx] = cost[cy][cx] + 1
            else:
                break


print(cost[gy - 1][gx - 1] if cost[gy - 1][gx - 1] != INF else -1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

h, w, k = LI()
sy, sx, gy, gx = LI()
cost = [[INF] * w for _ in range(h)]
cost[sy - 1][sx - 1] = 0
grid = SR(h)
q = deque([(sy - 1, sx - 1)])
while q:
    cy, cx = q.popleft()
    for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        for l in range(1, k + 1):
            ny, nx = cy + i * l, cx + j * l
            if 0 > nx or nx >= w or 0 > ny or ny >= h or grid[ny][nx] == "@":
                break
            if 0 <= cost[ny][nx] <= cost[cy][cx]:
                break
            if cost[ny][nx] == INF:
                q.append((ny, nx))
            cost[ny][nx] = cost[cy][cx] + 1


print(cost[gy - 1][gx - 1] if cost[gy - 1][gx - 1] != INF else -1)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

H,W,K=map(int,input().rstrip().split())
x1,y1,x2,y2=map(int,input().split())
c=[input().rstrip() for i in range(H)]
s=W*(x1-1)+y1-1
g=W*(x2-1)+y2-1

import heapq
que = []
d = [float("inf")] * (4*H*W)
d[4*s] = 0
heapq.heapify(que)
heapq.heappush(que, (0, 4*s))

while len(que) != 0:
    cost, v = heapq.heappop(que)
    if d[v] < cost: continue

    for j in range(4):
        nv=v-v%4+(v%4+j)%4
        if d[nv]>d[v]-d[v]%K+K*(d[v]%K>0):
            d[nv]=d[v]-d[v]%K+K*(d[v]%K>0)
            heapq.heappush(que,(d[nv],nv))

    i=v//4
    h,w=i//W,i%W
    if v%4==0:
        if h!=0 and c[h-1][w]==".":
            if d[v-4*W]>d[v]+1:
                d[v-4*W]=d[v]+1
                heapq.heappush(que,(d[v-4*W],v-4*W))
    elif v%4==2:
        if h!=H-1 and c[h+1][w]==".":
            if d[v+4*W]>d[v]+1:
                d[v+4*W]=d[v]+1
                heapq.heappush(que,(d[v+4*W],v+4*W))
    elif v%4==1:
        if w!=W-1 and c[h][w+1]==".":
            if d[v+4]>d[v]+1:
                d[v+4]=d[v]+1
                heapq.heappush(que,(d[v+4],v+4))
    else:
        if w!=0 and c[h][w-1]==".":
            if d[v-4]>d[v]+1:
                d[v-4]=d[v]+1
                heapq.heappush(que,(d[v-4],v-4))

ans=d[4*g]
if ans>=10**15:
    print(-1)
else:
    print(ans//K+(ans%K>0))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)

Submission status: Accepted

Solution code:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if 0 <= costs[px][py] < costs[x][y] + 1:
                break
            if costs[px][py] == -1:
                q.append((px, py))
            costs[px][py] = costs[x][y] + 1

print(costs[x2][y2])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")


def main(H, W, K, x1, y1, x2, y2, mapdata):
    start = x1 * W + y1
    goal = x2 * W + y2

    NUM_DIR = 4
    distances = [(INF, 0)] * (H * W * NUM_DIR)
    key = start * NUM_DIR
    distances[key] = (0, 0)
    distances[key + 2] = (0, 0)

    shortest_path = [0] * (H * W * NUM_DIR)
    shortest_path[key] = 0

    queue = [((0, 0), key), ((0, 0), key + 2)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, NUM_DIR)
        x, y = divmod(pos, W)
        dist = distances[pos_dir]
        if dist < (d, frac):
            continue
        if pos == goal:
            break

        dx, dy = DIRS[direction]
        nx = x + dx
        ny = y + dy
        # dp("nx, ny", nx, ny)
        if mapdata[nx * W + ny]:
            if frac == 0:
                newd = d + 1
                newfrac = -K + 1
            else:
                newd = d
                newfrac = frac + 1
            newdist = (newd, newfrac)
            to = (nx * W + ny) * NUM_DIR + direction

            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = pos_dir

        if direction < 2:
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * NUM_DIR + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * NUM_DIR + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * NUM_DIR + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * NUM_DIR + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

    result = min(distances[goal * NUM_DIR:goal * NUM_DIR + NUM_DIR])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

import heapq

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # surround the square with '@'
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = list('@' + input() + '@')
        c.append(i)
    c.append(['@'] * (w+2))


    from random import randrange
    if randrange(0, 3) == 0:
        # BFS
        # 直線を進めるだけ進む
        from collections import deque
        seen = [[0] * (w+2) for _ in range(h+2)]
        seen[x1][y1] = 1
        todo = deque([(x1, y1)])
 
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
 
        while len(todo) > 0:
            ix, iy = todo.popleft()
            s = seen[ix][iy] + 1
 
            for j in range(4):
                jx, jy = ix, iy
                dxj, dyj = dx[j], dy[j]
 
                for _ in range(k):
                    jx, jy = jx + dxj, jy + dyj
 
                    if c[jx][jy] == '@':
                        break
 
                    if jx == x2 and jy == y2:
                        print(s - 1)
                        exit()
            
                    if seen[jx][jy] == 0:
                        seen[jx][jy] = s
                        todo.append((jx, jy))



    # Dijkstra
    seen = [[-1] * (w+2) for _ in range(h+2)]
    # todo[i] == (cost, x, y, direction)
    todo = [(0, x1, y1, 0)]
    heapq.heapify(todo)

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    while len(todo) > 0:
        cost, xi, yi, direction = heapq.heappop(todo)

        # special case
        if seen[xi][yi] == cost:
            xj, yj = xi + dx[direction], yi + dy[direction]
            if c[xj][yj] == '.' and seen[xj][yj] == -1:
                heapq.heappush(todo, (cost+1, xj, yj, direction))
            continue

        if seen[xi][yi] != -1:
            continue
        seen[xi][yi] = cost

        # goal
        if xi == x2 and yi == y2:
            print((cost-1)//k + 1)
            exit()
        
        # add
        for j in range(4):
            xj, yj= xi + dx[j], yi + dy[j]

            if c[xj][yj] == '@':
                continue

            if seen[xj][yj] == -1:
                if j == direction:
                    heapq.heappush(todo, (cost+1, xj, yj, j))
                else:
                    heapq.heappush(todo, (((cost-1)//k + 1)*k + 1, xj, yj, j))

    print(-1)

main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = []
for _ in range(h):
    c.append(list(input()))
from collections import deque
def bfs(x, y):
    queue = deque([(x, y)])
    d = [[float('inf')]*w for _ in range(h)]
    d[x][y] = 0
    while queue:
        u, v = queue.popleft()
        # ↑
        for l in range(1, k + 1):
            p, q = u + l, v
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if d[u][v] + 1 > d[p][q]:
                break
            if d[p][q] == float("inf"):
                queue.append((p, q))
            d[p][q] = d[u][v] + 1
        for l in range(1, k + 1):
            p, q = u - l, v
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if d[u][v] + 1 > d[p][q]:
                break
            if d[p][q] == float("inf"):
                queue.append((p, q))
            d[p][q] = d[u][v] + 1
        for l in range(1, k + 1):
            p, q = u, v + l
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if d[u][v] + 1 > d[p][q]:
                break
            if d[p][q] == float("inf"):
                queue.append((p, q))
            d[p][q] = d[u][v] + 1
        for l in range(1, k + 1):
            p, q = u, v - l
            if not (0 <= p < h and 0 <= q < w) or c[p][q] == "@":
                break
            if d[u][v] + 1 > d[p][q]:
                break
            if d[p][q] == float("inf"):
                queue.append((p, q))
            d[p][q] = d[u][v] + 1
    return d
d = bfs(x1 - 1, y1 - 1)
if d[x2 - 1][y2 - 1] == float("inf"):
    print(-1)
else:
    print(d[x2 - 1][y2 - 1])

Submission status: Accepted

Solution code:
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = map(int, input().split())
sth, stw, glh, glw = map(int, input().split())

INF = 10**6 * K

dp = [[INF for _ in range(W + 2)] for _ in range(H + 2)]

dp[0] = [-1] * (W + 2)
dp[H + 1] = [-1] * (W + 2)
for h in range(1, H + 1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W + 1] = -1
    for w in range(1, W + 1):
        if s[w - 1] == "@":
            dp[h][w] = -1

dp[sth][stw] = 0


# Seen = [[INF]*W for _ in range(H)]
XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw))

    while len(next_q) != 0:
        # キュー取り出し(先頭)
        h, w = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K + 1):
                hs, ws = h + dh * sk, w + dw * sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws))
                    dp[hs][ws] = dp[h][w] + 1
                elif dp[hs][ws] <= dp[h][w]:
                    # もし、dp[hs][ws] が 今の値以下なら
                    # その先はdp[hs][ws]をもとに 書き込まれている or 今後書き込まれる ので止める
                    break
                # if hs == glh and ws == glw:
                #    return dp[h][w] + 1
    # return -1


def main():
    bfs(sth, stw, glh, glw)

    if dp[glh][glw] == INF:
        print(-1)
    else:
        print(dp[glh][glw])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = map(int, input().split())
sth, stw, glh, glw = map(int, input().split())

INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1, H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1, W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

dp[sth][stw] = 0


# Seen = [[INF]*W for _ in range(H)]
XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw))

    while len(next_q) != 0:
        # キュー取り出し(先頭)
        h, w = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws))
                    dp[hs][ws] = dp[h][w] + 1
                elif dp[hs][ws] <= dp[h][w]:
                    break
                if hs == glh and ws == glw:
                    return dp[h][w] + 1
    return -1


def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = map(int, input().split())
sth, stw, glh, glw = map(int, input().split())

INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1, H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1, W+1):
        if s[w-1] == "@":
            dp[h][w] = -1


# Seen = [[INF]*W for _ in range(H)]
XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw, 0))
    dp[sth][stw] = 0

    while len(next_q) != 0:
        # キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws, c+1))
                    dp[hs][ws] = c + 1
                elif dp[hs][ws] <= c:
                    break
                if hs == glh and ws == glw:
                    return c + 1
    return -1


def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

try:
    profile
except:
    def profile(f): return f

DEBUG = True
if DEBUG:
    def dp(*x):  # debugprint
        print(*x)
else:
    def dp(*x): pass


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # H, W, K = map(int, input().split())
    # x1, y1, x2, y2 = map(int, input().split())
    # mapdata = sys.stdin.buffer.read().splitlines()
    # print(data)
    start = x1 * W + y1
    goal = x2 * W + y2

    #distances = {}
    distances = [(INF, 0)] * (H * W * 5)
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances[pos_dir]
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        if direction < 2 or direction == 4:  # 0, 1, 4
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  # 2, 3, 4
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        # cur = pos_dir
        # while cur != start * 5 and cur != 0:
        #     pos, direction = divmod(cur, 5)
        #     x, y = divmod(pos, W)
        #     print(cur, x, y, direction, distances[cur])
        #     cur = shortest_path[cur]
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W, K = map(int, rl().split())
    sy, sx, gy, gx = map(lambda n: int(n) - 1, rl().split())
    c = [rl().rstrip() for _ in range(H)]
    
    INF = 10 ** 10
    cost = [[INF] * W for _ in range(H)]
    cost[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            for k in range(1, K + 1):
                ny, nx = cy + k * dy, cx + k * dx
                if 0 <= ny < H and 0 <= nx < W:
                    if c[ny][nx] == '@':
                        break
                    if cost[ny][nx] <= cost[cy][cx]:
                        break
                    ncost = cost[cy][cx] + 1
                    if ncost < cost[ny][nx]:
                        cost[ny][nx] = ncost
                        que.append((ny, nx))
    print(cost[gy][gx] if cost[gy][gx] != INF else -1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

h,w,k= map(int, input().split())
sx,sy,gx,gy= map(int, input().split())
maze= [list(input()) for i in range(h)]


# 迷路　BFS
def clear_maze(sx, sy, gx, gy):

    INF=10**9
    distance = [[INF for i in range(w)] for j in range(h)]
    #    distance = [[None]*field_x_length]*field_y_length
    def bfs():
        # きた点と方向を格納
        d=deque()
        d.append((sx, sy))
        distance[sx][sy] =0

        while len(d):
            x, y = d.popleft()

            for i in range(0, 4):
                for j in range(1,k+1):
                    nx, ny = x + [j, 0, -j, 0][i], y + [0, j, 0, -j][i]
                    if not (0 <= nx < h and 0 <= ny < w):
                        break

                    elif maze[nx][ny] == '@' or distance[nx][ny]<=distance[x][y]:
                        break

                    elif distance[nx][ny] == INF:
                        d.append((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1


        return distance[gx][gy]

    return bfs()

ans=clear_maze(sx-1,sy-1,gx-1,gy-1)

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