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


def bfs(xs, ys, d):
    queue = deque((xs, ys, d))
    M[xs][ys] = d
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1, d = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return

        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == "@":
                        break
                    elif M[x2][y2] == -1:  # まだ来たことない点だったという条件
                        M[x2][y2] = d + 1
                        queue.append((x2, y2))  # 新しい点を足す。
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

print(M[xg][yg])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.buffer.readlin
sqrt = math.sqrt
def LI(): return map(int, input().split())
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    mxy = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    h, w, K = LI()
    y1, x1, y2, x2 = LI()
    q = deque()
    field = [[False] * (w + 2)] + [None] * h + [[False] * (w + 2)]
    for i in range(1, h + 1):
        field[i] = [False] + [True] * w + [False]
    for i in range(1, h + 1):
        s = input()
        for j in range(1, w + 1):
            if s[j-1] == "@":
                field[i][j] = False
    q.append((x1, y1))
    ans = 0
    c = defaultdict(int)
    while q:
        next_q = deque()

        while q:
            x, y = q.popleft()
            if (x, y) == (x2, y2):
                print(ans)
                return
            if field[y][x]:
                for i in range(1, K + 1):
                    if field[y + i][x]:
                        if not c[(y + i, x)]:
                            next_q.append((x, y + i))
                            c[(y + i, x)] = 1
                    else:
                        break
                for i in range(1, K + 1):
                    if field[y][x + i]:
                        if not c[(y, x + i)]:
                            next_q.append((x + i, y))
                            c[(y, x + i)] = 1
                    else:
                        break
                for i in range(1, K + 1):
                    if field[y - i][x]:
                        if not c[(y - i, x)]:
                            next_q.append((x, y - i))
                            c[(y - i, x)] = 1
                    else:
                        break
                for i in range(1, K + 1):
                    if field[y][x - i]:
                        if not c[(y, x - i)]:
                            next_q.append((x - i, y))
                            c[(y, x - i)] = 1
                    else:
                        break
                field[y][x] = False
        ans += 1
        q = next_q
    print(-1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.Collection;
import java.io.IOException;
import java.util.Random;
import java.io.InputStreamReader;
import java.io.BufferedOutputStream;
import java.io.UncheckedIOException;
import java.nio.charset.Charset;
import java.util.StringTokenizer;
import java.util.concurrent.ThreadLocalRandom;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Queue;
import java.io.BufferedReader;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        LightWriter out = new LightWriter(outputStream);
        FPondSkater solver = new FPondSkater();
        solver.solve(1, in, out);
        out.close();
    }

    static class FPondSkater {
        private static final int REP = 5;
        private static final int INF = 1_000_000_000;

        public void solve(int testNumber, LightScanner in, LightWriter out) {
            int h = in.ints(), w = in.ints(), k = in.ints();
            int sy = in.ints() - 1, sx = in.ints() - 1, gy = in.ints() - 1, gx = in.ints() - 1;
            char[][] s = in.chars(h);
            int[][][] visited = new int[2][h][w];
            int[][] cost = new int[h][w];
            ArrayUtil.fill(cost, INF);
            cost[sy][sx] = 0;
            Queue<FPondSkater.P> q = new ArrayDeque<>();
            q.offer(new FPondSkater.P(sx, sy));
            while (!q.isEmpty()) {
                FPondSkater.P now = q.poll();
                int[] rand = {0, 1, 2, 3};
                ArrayUtil.shuffle(rand);
                for (int r : rand) {
                    switch (r) {
                        case 0:
                            if (visited[0][now.y][now.x] < REP) {
                                for (int d = 1; d <= k; d++) {
                                    if (now.x - d < 0
                                            || s[now.y][now.x - d] == '@'
                                            || visited[0][now.y][now.x - d] >= REP) break;
                                    if (d != k) visited[0][now.y][now.x - d]++;
                                    if (cost[now.y][now.x - d] > cost[now.y][now.x] + 1) {
                                        cost[now.y][now.x - d] = cost[now.y][now.x] + 1;
                                    }
                                    q.offer(new FPondSkater.P(now.x - d, now.y));
                                }
                            }
                            break;
                        case 1:
                            if (visited[0][now.y][now.x] < REP) {
                                for (int d = 1; d <= k; d++) {
                                    if (w <= now.x + d
                                            || s[now.y][now.x + d] == '@'
                                            || visited[0][now.y][now.x + d] >= REP) break;
                                    if (d != k) visited[0][now.y][now.x + d]++;
                                    if (cost[now.y][now.x + d] > cost[now.y][now.x] + 1) {
                                        cost[now.y][now.x + d] = cost[now.y][now.x] + 1;
                                    }
                                    q.offer(new FPondSkater.P(now.x + d, now.y));
                                }
                            }
                            break;
                        case 2:
                            if (visited[1][now.y][now.x] < REP) {
                                for (int d = 1; d <= k; d++) {
                                    if (now.y - d < 0
                                            || s[now.y - d][now.x] == '@'
                                            || visited[1][now.y - d][now.x] >= REP) break;
                                    if (d != k) visited[1][now.y - d][now.x]++;
                                    if (cost[now.y - d][now.x] > cost[now.y][now.x] + 1) {
                                        cost[now.y - d][now.x] = cost[now.y][now.x] + 1;
                                    }
                                    q.offer(new FPondSkater.P(now.x, now.y - d));
                                }
                            }
                            break;
                        case 3:
                            if (visited[1][now.y][now.x] < REP) {
                                for (int d = 1; d <= k; d++) {
                                    if (h <= now.y + d
                                            || s[now.y + d][now.x] == '@'
                                            || visited[1][now.y + d][now.x] >= REP) break;
                                    if (d != k) visited[1][now.y + d][now.x]++;
                                    if (cost[now.y + d][now.x] > cost[now.y][now.x] + 1) {
                                        cost[now.y + d][now.x] = cost[now.y][now.x] + 1;
                                    }
                                    q.offer(new FPondSkater.P(now.x, now.y + d));
                                }
                            }
                            break;
                    }
                }
                visited[0][now.y][now.x]++;
                visited[1][now.y][now.x]++;
            }
            out.ans(cost[gy][gx] == INF ? -1 : cost[gy][gx]).ln();
        }

        private static class P {
            int x;
            int y;

            P(int x, int y) {
                this.x = x;
                this.y = y;
            }

        }

    }

    static class LightScanner implements AutoCloseable {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public char[] chars() {
            return string().toCharArray();
        }

        public char[][] chars(int h) {
            char[][] res = new char[h][];
            for (int i = 0; i < h; i++) res[i] = chars();
            return res;
        }

        public int ints() {
            return Integer.parseInt(string());
        }

        public void close() {
            try {
                this.reader.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

    }

    static final class ArrayUtil {
        private ArrayUtil() {
        }

        public static void fill(int[] a, int v) {
            Arrays.fill(a, v);
        }

        public static void fill(int[][] a, int v) {
            for (int i = 0; i < a.length; i++) {
                fill(a[i], v);
            }
        }

        public static void shuffle(int[] array) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = array.length - 1; i > 0; i--) {
                int index = rnd.nextInt(i + 1);
                int tmp = array[index];
                array[index] = array[i];
                array[i] = tmp;
            }
        }

    }

    static class LightWriter implements AutoCloseable {
        private final Writer out;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter(Writer out) {
            this.out = out;
        }

        public LightWriter(OutputStream out) {
            this(new OutputStreamWriter(new BufferedOutputStream(out), Charset.defaultCharset()));
        }

        public LightWriter print(char c) {
            try {
                out.write(c);
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter print(String s) {
            try {
                out.write(s, 0, s.length());
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter ans(String s) {
            if (!breaked) {
                print(' ');
            }
            return print(s);
        }

        public LightWriter ans(int i) {
            return ans(Integer.toString(i));
        }

        public LightWriter ln() {
            print(System.lineSeparator());
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        public void close() {
            try {
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

    }
}

Submission status: Runtime Error

Solution code:
from collections import*
z,v,a,c=input,range,print,split
h,w,k=map(int,z().c());r,s,t,u=map(lambda x:int(x)-1,z().c())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft();j=l[x][y]
  if(x==t)&(y==u):exit(a(j))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=j:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=j+1
a(-1)

Submission status: Runtime Error

Solution code:
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft();j=l[x][y]
  if(x==t)&(y==u):exit(a(j))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=(c:=l[p][q])<=j:break
      if c<0:d+=[(p,q)];l[p][q]=j+1
a(-1)

Submission status: Runtime Error

Solution code:
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft();j=l[x][y]
  if(x==t)&(y==u):exit(a(j))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i;c=l[p][q]
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=v<=j:break
      if c<0:d+=[(p,q)];l[p][q]=j+1
a(-1)

Submission status: Runtime Error

Solution code:
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

Submission status: Runtime Error

Solution code:
z,v,a=input,range,print
h,w,k=map(int,z().split())
r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)]
l=[[-1]*w for _ in v(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      if not((0<=(p:=(x+e*i))<h)&(0<=(q:=(y+f*i))<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

Submission status: Runtime Error

Solution code:
z,v,a=input,range,print
h,w,k=map(int,z().split())
r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)]
l=[[-1]*w for _ in v(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      if not((0<=p:=(x+e*i)<h)&(0<=q:=(y+f*i)<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

Submission status: Runtime Error

Solution code:
z,v,a=input,range,print
h,w,k=map(int,z().split())
r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)]
l=[[-1]*w for _ in v(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      if not((0<=(p:=x+e*i)<h)&(0<=(q:=y+f*i)<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

Submission status: Runtime Error

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


def main():
    H, W, K = map(int, readline().split())
    sy, sx, gy, gx = map(int, readline().split())
    sy -= 1
    sx -= 1
    gx -= 1
    gy -=1
    lake = read().split()
    dist = [[INF] * W for _ in range(H)]
    dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    Q = deque()
    Q.append((sy, sx))
    dist[sy][sx] = 0
    while Q:
        y,x = Q.popleft()
        if (y,x) == (gy, gx):
            print(d[y][x])
            quit()
        for dx,dy in dxy:
            n_y = y
            n_x = x
            for _ in range(K):
                n_y +=dy
                n_x +=dx

                if 0<=n_x<W and 0<=n_y<H and lake[n_y][n_x] != '@':
                    if dist[n_y][n_x]<d[y][x]:
                        break
                    elif dist[n_y][n_x] == INF:
                        dist[n_y][n_x] = d[y][x] + 1
                        Q.append((n_y,n_x))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


def main():
    H, W, K = map(int, readline().split())
    sy, sx, gy, gx = map(int, readline().split())
    sy -= 1
    sx -= 1
    gx -= 1
    gy -=1
    lake = read().split()
    dist = [[INF] * W for _ in range(H)]
    dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    Q = deque()
    Q.append((sy, sx))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if (y,x) == (gy, gx):
            print(d[y][x])
            quit()
        for dx,dy in dxy:
            n_y = y
            n_x = x
            for _ in range(K):
                n_y +=dy
                n_x +=dx

                if 0<=n_x<W and 0<=n_y<H and lake[n_y][n_x] != '@':
                    if dist[n_y][n_x]<d[y][x]:
                        break
                    elif dist[n_y][n_x] == INF:
                        dist[n_y][n_x] = d[y][x] + 1
                        Q.append((n_y,n_x))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
inf=1000002
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([[x1-1,y1-1]])
dp[x1-1][y1-1]=0
def bfs(d):
    global dp,now
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    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_sub+=[[x,y+j,d]]
                cand+=[(x,y+j)]
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub+=[[x,y-j,d]]
                cand+=[(x,y-j)]
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub+=[[x+j,y,d]]
                cand+=[(x+j,y)]
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub+=[[x-j,y,d]]
                cand+=[(x-j,y)]
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now+=[i]
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

Submission status: Runtime Error

Solution code:
import sys
inf=1000002
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([[x1-1,y1-1]])
dp[x1-1][y1-1]=0
def bfs(d):
    global dp,now
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    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_sub+=[[x,y+j,d]]
                cand+=[(x,y+j)]
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub+=[[x,y-j,d]]
                cand+=[(x,y-j)]
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub+=[[x+j,y,d]]
                cand.+=[(x+j,y)]
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub+=[[x-j,y,d]]
                cand+=[(x-j,y)]
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now+=[i]
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

Submission status: Runtime Error

Solution code:
import sys
inf=1000002
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([x1-1,y1-1])
dp[x1-1][y1-1]=0
def bfs(d):
    global dp,now
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    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_sub.append([x,y+j,d])
                cand.add((x,y+j))
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                cand.add((x,y-j))
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                cand.add((x+j,y))
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                cand.add((x-j,y))
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

Submission status: Runtime Error

Solution code:
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 = deque()
ds = [9999999999999999] * (h*w)

q.append((x1, y1))
ds[x1*w+y1] = 0
dr = (1, 0, -1, 0)
dc = (0, 1, 0, -1)
while len(q) > 0:
    r, c = q.popleft()
    for i in range(4):
        for j in range(1, K+1):
            nr, nc = r + dr[i] * j, c + dc[i] * j
            if 0 <= nr < h and 0 <= nc < w and bd[nr][nc] != "@":
                nd = ds[r*w+c] + 1
                if nd < ds[nr*w+nc]:
                    ds[nr*w+nc] = nd
                    q.append((nr, nc))
                elif nd <= ds[nr*w+nc]:
                    continue
                else:
                    break
            else:
                break
ans = ds[x2*w+y2]
if ans < 999999999999:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
inf=1000002
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]*w for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
def bfs(d):
    global h,w,k,x1,y1,x2,y2,c,dp,now
    l=len(now)
    if l==0:
        return
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,max(k+1,w-y)):
            if c[x][y+j]==".":
                if dp[x][y+j]==inf:
                    dp[x][y+j]=d
                    now.append([x,y+j])
            else:
                break
        for j in range(1,max(k+1,y+1)):
            if c[x][y-j]==".":
                if dp[x][y-j]==inf:
                    dp[x][y-j]=d
                    now.append([x,y-j])
            else:
                break
        for j in range(1,max(k+1,h-x)):
            if c[x+j][y]==".":
                if dp[x+j][y]==inf:
                    dp[x+j][y]=d
                    now.append([x+j,y])
            else:
                break
        for j in range(1,max(k+1,x+1)):
            if c[x-j][y]==".":
                if dp[x-j][y]==inf:
                    dp[x-j][y]=d
                    now.append([x-j,y])
            else:
                break
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


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


def main():
    h, w, k = map(int, input().strip().split())
    x1, y1, x2, y2 = map(int, input().strip().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    m = []
    costs1 = [[None for j in range(w)] for i in range(h)]
    costs2 = [[None for j in range(w)] for i in range(h)]
    for _ in range(h):
        m.append(list(input().strip()))
    q1 = deque()
    q1.append((x1, y1, 0))
    costs1[x1][y1] = 0
    q2 = deque()
    q2.append((x2, y2, 0))
    costs2[x2][y2] = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while q1 and q2:
        (x, y, cost) = q1.popleft()
        if not costs2[x][y] is None:
            print(cost + costs2[x][y])
            return
        for (add_x, add_y) in directions:
            for dist in range(1, k + 1):
                new_x = x + add_x * dist
                new_y = y + add_y * dist
                if new_x >= h or new_x < 0 or new_y >= w or new_y < 0 or m[new_x][new_y] == '@' or costs1[new_x][new_y] < cost + 1:
                    break
                if costs1[new_x][new_y] is None:
                    costs1[new_x][new_y] = cost + 1
                    q1.append((new_x, new_y, cost + 1))
        (x, y, cost) = q2.popleft()
        if not costs1[x][y] is None:
            print(cost + costs1[x][y])
            return
        for (add_x, add_y) in directions:
            for dist in range(1, k + 1):
                new_x = x + add_x * dist
                new_y = y + add_y * dist
                if new_x >= h or new_x < 0 or new_y >= w or new_y < 0 or m[new_x][new_y] == '@' or costs2[new_x][new_y] < cost + 1:
                    break
                if costs2[new_x][new_y] is None:
                    costs2[new_x][new_y] = cost + 1
                    q2.append((new_x, new_y, cost + 1))
    print("-1")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from math import sqrt
from heapq import heappush, heappop
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    M, N, K = it()
    x1, y1, x2, y2 = it()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    grid = [list(input().strip()) for _ in range(M)]

    ans = INF
    pq = [(0, 0, 0, x1, y1)]
    while pq:
        moves, accum, direc, x, y = heappop(pq)
        assert accum < K
        if x == x2 and y == y2:
            ans = min(ans, moves if accum == 0 else moves + 1)
            continue
        if grid[x][y] == '@':
            continue
        if moves > ans:
            break
        grid[x][y] = '@'
        for x0, y0, d0 in ((x - 1, y, 1), (x + 1, y, 2), (x, y - 1, 3), (x, y + 1, 4)):
            if 0 <= x0 < M and 0 <= y0 < N and grid[x0][y0] != '@':
                new_moves = moves
                new_accum = accum
                if direc == d0 or direc == 0:
                    new_accum += 1
                    if new_accum == K:
                        new_moves += 1
                        new_accum = 0
                else:
                    if new_accum > 0:
                        new_moves += 1
                    new_accum = 1
                heappush(pq, (new_moves, new_accum, d0, x0, y0))
    return -1 if ans == INF else ans
    

if __name__ == '__main__':
    print(solve())