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: Runtime Error

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

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

x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1

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

update_list = deque([(x1, y1)])

while len(update_list) != 0:

    cord = update_list[0]
    x, y = cord[0], cord[1]
    update_list.popleft()
    tmp_step = step_map[x][y]

    # up
    for i in range(1, K+1, 1):
        if x - i < 0:
            break
        if pond[x-i][y] == '@' or (step_map[x-i][y] != INF and step_map[x-i][y] != tmp_step + 1):
            break
        step_map[x-i][y] = tmp_step + 1
        update_list.append((x-i, y))

    # down
    for i in range(1, K + 1, 1):
        if x + i >= H:
            break
        if pond[x + i][y] == '@' or (step_map[x + i][y] != INF and step_map[x + i][y] != tmp_step + 1):
            break
        step_map[x + i][y] = tmp_step + 1
        update_list.append((x + i, y))

    # left
    for i in range(1, K + 1, 1):
        if y - i < 0:
            break
        if pond[x][y - i] == '@' or (step_map[x][y - i] != INF and step_map[x][y - i] != tmp_step + 1):
            break
        step_map[x][y - i] = tmp_step + 1
        update_list.append((x, y - i))

    # right
    for i in range(1, K + 1, 1):
        if y + i > W:
            break
        if pond[x][y + i] == '@' or (step_map[x][y + i] != INF and step_map[x][y + i] != tmp_step + 1):
            break
        step_map[x][y + i] = tmp_step + 1
        update_list.append((x, y + i))

    if step_map[x2][y2] != 0:
        print(step_map[x2][y2])
        exit()


print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

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

x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1

step_map = np.zeros((H, W), dtype=np.int)

for h in range(H):
    tmp = input()
    for w in range(W):
        if tmp[w] == '@':
            step_map[h][w] = -1

update_list = deque([(x1, y1)])

while len(update_list) != 0:

    cord = update_list[0]

    x, y = cord[0], cord[1]
    update_list.popleft()
    tmp_step = step_map[x][y]

    # up
    for i in range(1, K+1, 1):
        if x - i < 0:
            break
        if step_map[x-i][y] != 0 and step_map[x-i][y] != tmp_step + 1:
            break
        step_map[x-i][y] = tmp_step + 1
        update_list.append((x-i, y))

    # down
    for i in range(1, K + 1, 1):
        if x + i >= H:
            break
        if step_map[x + i][y] != 0 and step_map[x + i][y] != tmp_step + 1:
            break
        step_map[x + i][y] = tmp_step + 1
        update_list.append((x + i, y))

    # left
    for i in range(1, K + 1, 1):
        if y - i < 0:
            break
        if step_map[x][y - i] != 0 and step_map[x][y - i] != tmp_step + 1:
            break
        step_map[x][y - i] = tmp_step + 1
        update_list.append((x, y - i))

    # right
    for i in range(1, K + 1, 1):
        if y + i > W:
            break
        if step_map[x][y + i] != 0 and step_map[x][y + i] != tmp_step + 1:
            break
        step_map[x][y + i] = tmp_step + 1
        update_list.append((x, y + i))

    if step_map[x2][y2] != 0:
        print(step_map[x2][y2])
        exit()


print(-1)

Submission status: Runtime Error

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

@profile
def main():
    from heapq import heappush, heappop, heapify
    H, W, K = MAP()
    HH = max(H, W) + 2
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]

    # 0123: 上下左右
    stack = []
    heappush(stack, (0, x1, y1, 0))
    heappush(stack, (0, x1, y1, 1))
    heappush(stack, (0, x1, y1, 2))
    heappush(stack, (0, x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        new_stack = []
        while stack:
            curr, x, y, d = heappop(stack)
            dx, dy = DX[d], DY[d]
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * dx, y + k * dy
                if c[xx][yy] == 0:
                    b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d - 1) % 4))
                    b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d + 1) % 4))
                    c[xx][yy] = a
                elif c[xx][yy] != a:
                    flag = False
                    break
            if flag:
                heappush(new_stack, (a, xx, yy, d))
            if c[x2][y2] > 0:
                print(c[x2][y2], flush=True)
                exit(0)
        stack = new_stack

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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


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

    # 0123: 上下左右
    stack = [((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
             ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        head = 0
        new_stack = []
        while head < len(stack):
            b = stack[head]
            d = b % 4
            x, y = divmod(b >> 2, KETA)
            head += 1
            flag = True
            a = c[x][y] + 1
            for k in range(1, K + 1):
                xx, yy = x + k * DX[d], y + k * DY[d]
                if not (c[xx][yy] == 0 or c[xx][yy] == a):
                    flag = False
                    break
                if (xx, yy) == (x2, y2):
                    print(a)
                    return
                new_stack.append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                new_stack.append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                updated.append((a, xx, yy))
            if flag:
                new_stack.append(((xx * KETA + yy) << 2) + d)
        stack = new_stack
        for a, xx, yy in updated:
            c[xx][yy] = a
        update = []

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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


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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**7]*w for _ in range(w)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or w <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

h, w, k = nm()
sy, sx, gy, gx = nm()
d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
sx -= 1; sy -= 1
gx -= 1; gy -= 1
C = [ns() for _ in range(w)]
G = [[10**10]*w for _ in range(h)]
G[sy][sx] = 0
q = deque([(sy, sx)])
while q:
    y, x = q.popleft()
    for i in range(4):
        dy, dx = d[i]
        ny, nx = y, x
        for _ in range(k):
            ny += dy; nx += dx
            if ny < 0 or h <= ny or nx < 0 or w <= nx:
                break
            if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                break
            if G[ny][nx] > G[y][x] + 1:
                G[ny][nx] = G[y][x] + 1
                q.append((ny, nx))
ans = G[gy][gx]
print(ans if ans < 10**10 else -1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**10]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**10 else -1)
    return

solve()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    geta = 20
    mask = (1 << geta) - 1
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**10]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy<<geta) + sx])
    while q:
        v = q.popleft()
        y = v >> geta; x = v & mask
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx or C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny<<geta) + nx)
    ans = G[gy][gx]
    print(ans if ans < 10**10 else -1)
    return

solve()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[10**10]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx or C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**10 else -1)
    return

solve()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< ll, ll >
#define piiii pair<ll,pair<ll,pii>>
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
void  solve(){
  ll h,w,k,x1,x2,y1,y2;
  char kl;

  cin>>h>>w>>k;
  cin>>x1>>y1>>x2>>y2;
  x1--,y1--,x2--,y2--;

  vector<vector<ll>> a(h,vector<ll>(w,0));
  rep(i,0,h) rep(j,0,w){cin>>kl; if(kl=='.') a[i][j]=1;}

  vector<pii> direction ={{1,0},{0,1},{-1,0},{0,-1}};

  vector<vector<ll>> dp(h,vector<ll>(w,1e18));
  priority_queue<piiii,vector<piiii> ,greater<piiii>> pq;

  dp[x1][y1]=0;
  pii pos={x1,y1};
  if(pos.f>0 && a[pos.f-1][pos.s]==1) pq.push({1,{2,{pos.f-1,pos.s}}}),dp[pos.f-1][pos.s] = 1;
  if(pos.s>0 && a[pos.f][pos.s-1]==1) pq.push({1,{3,{pos.f,pos.s-1}}}),dp[pos.f][pos.s-1] = 1;
  if(pos.f+1<h && a[pos.f+1][pos.s]==1) pq.push({1,{0,{pos.f+1,pos.s}}}),dp[pos.f+1][pos.s] = 1;
  if(pos.s+1<w && a[pos.f][pos.s+1]==1) pq.push({1,{1,{pos.f,pos.s+1}}}),dp[pos.f][pos.s+1] = 1;

  while(!pq.empty()){
      piiii top=pq.top();
      pq.pop();
      pos = top.s.s;
      ll val=top.f,val1=val;
      ll dire=top.s.f;

      if(dp[pos.f][pos.s]<=val+2*k) continue;
//if(pos.f == x2 && pos.s == y2) break;
      dp[pos.f][pos.s]=min(dp[pos.f][pos.s],val);

      if(pos.f>0 && a[pos.f-1][pos.s]==1) {
        val1=val;
        if(dire != 2) val1=ceil((val*1.0)/k)*k;
        if(dp[pos.f-1][pos.s]+2*k>=val1+1)pq.push({val1+1,{2,{pos.f-1,pos.s}}});
      }
      if(pos.s>0 && a[pos.f][pos.s-1]==1) {
        val1=val;
        if(dire != 3) val1=ceil((val*1.0)/k)*k;
        if(dp[pos.f][pos.s-1]+2*k>=val1+1)pq.push({val1+1,{3,{pos.f,pos.s-1}}});
      }
      if(pos.f+1<h && a[pos.f+1][pos.s]==1) {
        val1=val;
        if(dire != 0) val1=ceil((val*1.0)/k)*k;
        if(dp[pos.f+1][pos.s]+2*k>=val1+1)pq.push({val1+1,{0,{pos.f+1,pos.s}}});
      }
      if(pos.s+1<w && a[pos.f][pos.s+1]==1) {
        val1=val;
        if(dire != 1) val1=ceil((val*1.0)/k)*k;
        if(dp[pos.f][pos.s+1]+2*k>=val1+1) pq.push({val1+1,{1,{pos.f,pos.s+1}}});
      }
  }
  // cout<<dp[x2][y2]<<endl;
  if(dp[x2][y2]==1e18) cout<<-1<<endl;
  else cout<<(ll) (ceil(1.0*dp[x2][y2]/k))<<endl;
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< ll, ll >
#define piiii pair<ll,pair<ll,pii>>
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
void  solve(){
  ll h,w,k,x1,x2,y1,y2;
  char kl;

  cin>>h>>w>>k;
  cin>>x1>>y1>>x2>>y2;
  x1--,y1--,x2--,y2--;

  vector<vector<ll>> a(h,vector<ll>(w,0));
  rep(i,0,h) rep(j,0,w){cin>>kl; if(kl=='.') a[i][j]=1;}

  vector<pii> direction ={{1,0},{0,1},{-1,0},{0,-1}};

  vector<vector<ll>> dp(h,vector<ll>(w,1e18));
  priority_queue<piiii,vector<piiii> ,greater<piiii>> pq;

  dp[x1][y1]=0;
  pii pos={x1,y1};
  if(pos.f>0 && a[pos.f-1][pos.s]==1) pq.push({1,{2,{pos.f-1,pos.s}}});
  if(pos.s>0 && a[pos.f][pos.s-1]==1) pq.push({1,{3,{pos.f,pos.s-1}}});
  if(pos.f+1<h && a[pos.f+1][pos.s]==1) pq.push({1,{0,{pos.f+1,pos.s}}});
  if(pos.s+1<w && a[pos.f][pos.s+1]==1) pq.push({1,{1,{pos.f,pos.s+1}}});

  while(!pq.empty()){
      piiii top=pq.top();
      pq.pop();
      pos = top.s.s;
      ll val=top.f,val1=val;
      ll dire=top.s.f;

      if(dp[pos.f][pos.s]<=val+2*k) continue;
if(pos.f == x2 && pos.s == y2) break;
      dp[pos.f][pos.s]=min(dp[pos.f][pos.s],val);

      if(pos.f>0 && a[pos.f-1][pos.s]==1) {
        val1=val;
        if(dire != 2) val1=ceil((val*1.0)/k)*k;
        if(dp[pos.f-1][pos.s]+2*k>=val1+1)pq.push({val1+1,{2,{pos.f-1,pos.s}}});
      }
      if(pos.s>0 && a[pos.f][pos.s-1]==1) {
        val1=val;
        if(dire != 3) val1=ceil((val*1.0)/k)*k;
        if(dp[pos.f][pos.s-1]+2*k>=val1+1)pq.push({val1+1,{3,{pos.f,pos.s-1}}});
      }
      if(pos.f+1<h && a[pos.f+1][pos.s]==1) {
        val1=val;
        if(dire != 0) val1=ceil((val*1.0)/k)*k;
        if(dp[pos.f+1][pos.s]+2*k>=val1+1)pq.push({val1+1,{0,{pos.f+1,pos.s}}});
      }
      if(pos.s+1<w && a[pos.f][pos.s+1]==1) {
        val1=val;
        if(dire != 1) val1=ceil((val*1.0)/k)*k;
        if(dp[pos.f][pos.s+1]+2*k>=val1+1) pq.push({val1+1,{1,{pos.f,pos.s+1}}});
      }
  }
  // cout<<dp[x2][y2]<<endl;
  if(dp[x2][y2]==1e18) cout<<-1<<endl;
  else cout<<(ll) (ceil(1.0*dp[x2][y2]/k))<<endl;
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}

Submission status: Runtime Error

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]ord[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    h, w, k = MI()
    x1, y1, x2, y2 = MI()
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    mylist = [0] * h

    #tableの読み込み
    for i in range(h):
        temp = input().rstrip()
        temp = [temp[j] for j in range(w)]
        mylist[i] = temp
    #初期化
    distance = [[float('inf') for i in range(w)] for j in range(h)]
    distance[x1][y1] = 0
    d = deque()
    start = (x1, y1)
    goal = [x2, y2]
    d.append(start)
    move = ([-1,0],[1,0],[0,1],[0,-1])

    while d:
        pos = d.pop()
        x = pos[0]
        y = pos[1]
        if x == x2 and y == y2:
            break
        dist = distance[x][y]
        for i in move:
            #tempxの初期化
            tempx = x
            tempy = y
            for l in range(k):
                tempx += i[0]
                tempy += i[1]
                if not ((tempx >= 0 and tempx <= h-1) and (tempy >= 0 and tempy <= w - 1)):
                    break
                if dist + 1 < distance[tempx][tempy] and mylist[tempx][tempy] == ".":
                    distance[tempx][tempy] = dist + 1
                    d.append((tempx, tempy))
                else:
                    break
    if distance[x2][y2] == float('inf'):
        print(-1)
    else:
        print(distance[x2][y2])
        
main()
#関数リスト
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    h, w, k = MI()
    x1, y1, x2, y2 = MI()
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    mylist = [0] * h

    #tableの読み込み
    for i in range(h):
        temp = input().rstrip()
        temp = [temp[j] for j in range(w)]
        mylist[i] = temp
    #初期化
    distance = [[float('inf') for i in range(w)] for j in range(h)]
    distance[x1][y1] = 0
    d = deque()
    start = (x1, y1)
    goal = [x2, y2]
    d.append(start)
    move = ([-1,0],[1,0],[0,1],[0,-1])

    while d:
        pos = d.pop()
        x = pos[0]
        y = pos[1]
        if x == x2 and y == y2:
            break
        dist = distance[x][y]
        for i in move:
            #tempxの初期化
            tempx = x
            tempy = y
            for l in range(k):
                tempx += i[0]
                tempy += i[1]
                if not ((tempx >= 0 and tempx <= h-1) and (tempy >= 0 and tempy <= w - 1)):
                    break
                if dist + 1 < distance[tempx][tempy] and mylist[tempx][tempy] == ".":
                    distance[tempx][tempy] = dist + 1
                    d.append((tempx, tempy))
                else:
                    break
    if distance[x2][y2] == float('inf'):
        print(-1)
    else:
        print(distance[x2][y2])
        
main()

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    h, w, k = MI()
    x1, y1, x2, y2 = MI()
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    mylist = [0] * h

    #tableの読み込み
    for i in range(h):
        temp = input().rstrip()
        temp = [temp[j] for j in range(w)]
        mylist[i] = temp
    #初期化
    distance = [[float('inf') for i in range(w)] for j in range(h)]
    distance[x1][y1] = 0
    d = deque()
    start = tuple(x1, y1)
    goal = [x2, y2]
    d.append(start)
    move = tuple([-1,0],[1,0],[0,1],[0,-1])

    while d and index <= k:
        pos = d.pop()
        x = pos[0]
        y = pos[1]
        dist = distance[x][y]
        for i in move:
            #tempxの初期化
            tempx = x
            tempy = y
            for l in range(k):
                tempx += i[0]
                tempy += i[1]
                if not ((tempx >= 0 and tempx <= h-1) and (tempy >= 0 and tempy <= w - 1)):
                    break
                if dist + 1 < distance[tempx][tempy] and mylist[tempx][tempy] == ".":
                    distance[tempx][tempy] = dist + 1
                    d.append(tuple(tempx, tempy))
                else:
                    break
    if distance[x2][y2] == float('inf'):
        print(-1)
    else:
        print(distance[x2][y2])
        
main()